Among your web of friends and acquaintances, you can probably keep track of who knows whom without resorting to complicated mathematics. But look at the millions of people on Facebook and other social networking sites, and you probably need all the math tools you can find to map out the myriad connections among them.
Helping to untangle the worlds-within-worlds connections that comprise social networks is among the potential benefits of Preeti Mohindru’s recently completed doctoral thesis at Guelph. She says her work in matrix theory might ultimately help software engineers and programmers in designing or improving sites such as Facebook, Twitter and LinkedIn.
In the process, Mohindru also accomplished something unusual for a PhD candidate: she proved a mathematical conjecture that had gone without a formal proof for two decades.
A mathematical conjecture is a statement that appears to be true but has yet to be formally proved. When someone comes up with a proof, that conjecture becomes a theorem, such as the Pythagorean Theorem relating the lengths of a triangle’s sides.
Sometimes it can take centuries for a conjecture to be proved. One of the most notable theorems in mathematical history, Fermat’s Last Theorem, was proved in 1994 – more than three centuries after its conjecture.
That was the same year that three mathematicians came up with another conjecture involving matrices, or arrays of numbers or symbols arranged in rows and columns. Their conjecture was actually disproved by other experts, but not necessarily for all types of matrices.
When Mohindru started her doctorate in early 2012, Prof. Rajesh Pereira, Mathematics and Statistics, suggested a few problems to tackle, including this Drew-Johnson-Loewy Conjecture.
Mohindru showed their conjecture holds for an exotic group of so-called completely positive matrices, or grids containing no negative entries.
Pereira says the problem “was a famous open conjecture for 20 years before being disproved by a group of mathematicians. What Preeti has done is to show that the Drew-Johnson-Loewy conjecture is actually true.”
Mohindru’s work might provide a tool for solving various real-life problems, including mapping and understanding connections among users of social networks. Within those networks, she says, some users are connected directly. Others are connected through mutual acquaintances.
“How many different groups do we need to cover the whole Facebook matrix so that, in every group, everyone talks with every other, and one person can be in more than one group?” she says. “What’s the minimum number of groups we need?”
To illustrate, Mohindru sketches seven dots for “users” on a piece of paper, with lines connecting some and not others. Her simple example yields five discrete groupings of connected users – easy enough to work out on paper.
Multiply the numbers by millions – for Facebook users, for example – and you would need a computer to churn through all of the data and come up with matrices of information describing a vast number of relationship groups. By offering ways to trace and quantify groups of related users, her research could benefit programmers designing and maintaining such sites.
Mohindru did most of her own research by sketching out matrices and math theories with pencil and paper.
A key moment came one day in 2013 in San Jose, California, where she lives with her husband, Vijay Kumar Kukreja. She spent summers there during her grad studies, communicating with her supervisor through Skype. She spent one day working as usual in the San Jose library.
“After dinner one day, I was lying on the couch and trying to see where I was stuck,” she says. Poring over her paperwork, she had a brainwave about her matrices and their entries. That opened the way to proving the conjecture.
Or most of it. Stuck near the end, she brought her work back to Guelph that fall and enlisted Pereira’s help to finish the project. She published the results in a paper this year in the journal Linear and Multi-Linear Algebra.
She figures her late grandfather, an engineer, would have approved. Growing up in northern India, she always looked forward to report card day. Good marks brought 20 rupees from her grandfather to each of his grandchildren; Preeti always got 100 rupees, because she did so well in mathematics.
“He always taught me nothing was better than learning. He was very good at math,” says Mohindru. Sketching symbols with her hand, she adds, “He taught me to do percentages in the air.”
She completed undergrad and master’s degrees in India. In 2008, her family came to Canada and settled in Vancouver. Mohindru came to Guelph for a second master’s degree in mathematics and statistics before pursuing her PhD.
What would grandfather say about her completing her doctorate – and proving a mathematical conjecture? “He would be very happy. He will tell everyone in that village: ‘See my granddaughter, she did her PhD.’”