Ode To The Math Monthly

Some fun results on matrices

Olga Taussky-Todd was one of the leading experts on all things related to matrix and linear algebra in the middle and late 1900′s. She was born in the Austro-Hungarian Empire in what is now the Czech Republic, and obtained her doctorate in Vienna in 1930. She attended the Vienna Circle while fellow student Kurt Gödel was proving his greatest results, and recalled that Gödel was very much in demand for help with mathematical problems of all kinds. She left Austria in 1934, worked a year at Bryn Mawr near Philadelphia, then held appointments at the universities of Cambridge and London until after World War II, when she and her husband John Todd emigrated to America.

Today I want to present a couple of simple, but very cool results about matrices.

Taussky-Todd once said in the American Mathematical Monthly—from now on the Monthly:

I did not look for matrix theory. It somehow looked for me.

That is to say, her doctorate was on algebraic number theory, and then she progressed to functional analysis. Heading in the direction of continuous mathematics was the available path. According to these biographical notes, the field of matrix theory did not really exist at the time. The notes hint that matrix theory was too light to be a main subject for graduate education unto itself, so perhaps the Monthly was a needed vehicle to help to launch it.

Matrix and Monthly

One of Taussky-Todd’s great papers is “A recurring theorem in determinants,” which proved a variety of simple, but fundamental, theorems about matrices. It appeared, as did many of her papers, in the Monthly. One of these theorems is a famous non-singularity condition:

Theorem: Let be a complex matrix, and let stand for the sum of the absolute values of the non-diagonal elements in row , namely

If is diagonally dominant, meaning.

then

I recall as a student “meeting” Taussky-Todd’s work in a book on algebraic number theory. Somehow many of the results in that area could be reconstructed as theorems on matrices, and the resulting proofs sometimes were much more transparent.

Ivars Peterson has a nice discussion of her work here. The same biographical notes referenced above have this revealing passage:

Olga Taussky always wished to ease the way of younger women in mathematics, and was sorry not to have more to work with. She said so, and she showed it in her life. Marjorie Senechal recalls giving a paper at an AMS meeting for the first time in 1962, and feeling quite alone and far from home. Olga turned the whole experience into a pleasant one by coming up to Marjorie, all smiles introducing herself, and saying, “It’s so nice to have another woman here! Welcome to mathematics!”

Let’s look at two simple but I believe interesting results about matrices. One is from the Monthly, and perhaps Olga would appreciate them.

A Matrix Result

Consider the two matrices and over the integers:

The question is it possible for a sequence of ‘s and ‘s to equal another distinct sequence of ‘s and ‘s? For example, is:

The answer is , and see the next paragraph for the cool proof. One way to think about this is that the two matrices generate the free semigroup. There are pairs of matrices that generate the free group, but the proof that they do that is harder, in my opinion. I once used that the free group is generated by matrices to solve an open problem—see here. What is cool is that the proof is quite unexpected.

The key is to look at the action of the matrices on positive vectors: the vector is positive provided

where and . Note that both and map positive vectors to positive vectors.

Also define to be those vectors whose first coordinate is strictly larger than its second and define to be those whose second coordinate is strictly larger than its first. Thus,

Let and be distinct sequences of the matrices and that are equal: we plan to show that . If they both start with the same matrix, since the matrices are invertible, we can find shorter such sequences. Thus, we can assume that and for some and . Let be any positive vector. Define

It follows that both vectors and are positive. But we note that is in and is in , which is impossible since by assumption.

This neat argument is due to Reiner Martin answering a question in the Monthly—the question was raised by Christopher Hillar and Lionel Levine.

Another Matrix Result

There are many normal forms for matrices of all kinds. I recently ran into the following question, which was quickly solved by Mikael de la Salle. Let be an matrix. Prove that there is a and two unitary matrices and so that

This says that any matrix, up to scaling, is the average of two unitary matrices. It seems this should be a useful fact, but I have not applied it yet.

We can find unitary matrices and and a real diagonal matrix so that

This is the famous Singular Value Decomposition. We can assume that the values on the diagonal are all at most in absolute value, by using to re-scale if needed. The key is that

where each and are unitary. This insight is based on the fact that if for a real , then there is a real so that

where has absolute value . This follows since there is a real so that . We can now use this term-by-term on the diagonal of to construct the diagonal matrices and . Then it follows that

Open Problems

Which matrices are averages—or sums—-of some given fixed number of unitary matrices? With , that is. Is there a good way to characterize them?

Do you have your own favorite matrix results that have a simple proof, but may not be well known to all? If so please share them with all of us.

Finally, I would suggest that you read the Monthly regularly, since it is filled with gems.

Is it Time to Declare Victory in Counting Complexity?

The last dichotomy theorem: graph homomorphism with complex values

Jin-Yi Cai is a great theorist, a world expert on Dichotomy Theorems, and a best friend. We have talked about him before here for his work on these types of theorems, and more recently here.

Today is a new type of post for us—a guest post, by Jin-Yi. We have used his suggested post title, but have inserted a couple sections for added background.

It’s Still the Slime Mold Story

Short paths for love and glory as time goes by

Kurt Mehlhorn is a theorist who has made many contributions to almost all aspects of theory. A recurrent theme is the balance of beautiful theory with potential practical applications—most of his work has some of each. He has made contributions to: data structures, computational geometry, parallel computing, VLSI design, computational complexity, combinatorial optimization, and graph algorithms. He is famous beyond the theory community for his work on LEDA, the Library of Efficient Data types and Algorithms. And he has also been the director of the Max Planck Institute for Computer Science.

Today Ken and I want to talk about yet another paper on slime mold—when will these papers stop?

What Makes a Knot Knotty?

Can it be just the not-ation?

Colin Rourke is a topologist at the University of Warwick in England. He is one of numerous mathematicians whose work is surveyed in an entertaining article by Sam Nelson of the Claremont Colleges in California, “The Combinatorial Revolution in Knot Theory” which appeared in last month’s AMS Notices. Rourke’s home page has interesting materials and notes besides a selection of his papers. These include a one-page formulation of Gödel’s first incompleteness theorem and a model for the universe that “overturns nearly every tenet of current cosmology.”

Today Dick and I wish to draw attention to the mathematical structures in Nelson’s article, whose properties have been developed by Rourke and others, and to how syntax may take precedence over the ‘real physical meaning’ of a mathematical concept.

2012 Survey Results

What would your favorite theoretician be doing?

Antea is a fictional young aspiring mathematical physicist in the epilogue of Roger Penrose’s book The Road to Reality. She experienced the rare green flash phenomenon while watching the sunrise, and “then an odd [remarkable] thought overtook her…”

Today we wish to thank the 259 people who took our survey posted last week, and present the results. Of course Antea could not be among the great thinkers listed, not at that stage, but our purpose was to see where the greats would seek remarkable thoughts today.

Predictions For 2012

Possibly excepting the last 10 days

Joseph T. Goodman became the owner and editor of a newspaper in Virginia City, Nevada called the Territorial Enterprise, a few years after its founding in 1858. He furthered the circulation of the newspaper throughout the Western territories, and used it as a mouthpiece for positions such as supporting the Union in the Civil War. In his day one could say that this amounted to a prediction. One of his later efforts was to grow grapes in Northern California, and though his own effort seems to have had no memorable yield, one can say he predicted the area would be good for wine.

Today we wish to go over last year’s predictions, and offer a mostly new slate for 2012. The supposed Mayan prediction of the end of the world on December 21st, 2012 makes us hedge by not venturing anything beyond that date.

A 2012 Survey

Questions we must ask

The Harrisburg Pennsylvanian, a newspaper, conducted one of the earliest political polls. Their poll in 1824 correctly showed Andrew Jackson leading John Quincy Adams by 335 votes to 169 in the contest for the United States Presidency.

Today I want to discuss the future of GLL, since 2012 is potentially a special year.

The Name Game

A little trick with Nick

John Doe is not a theorist, but was once the name used as a place holder for everyone.

Today Ken and I want to thank everyone who reads GLL, including John Doe.

Proofs, Proofs, and Proofs

Your proof is not my proof

Jennifer Chayes is theorist who has made fundamental contributions in two different ways, some directly as a researcher and some indirectly as a manager. She is the director and co-founder of the Microsoft research lab in Cambridge—the one in New England—not England. Her main research contributions are in the area that spans theory and physics, including phase transitions in discrete systems such as networks. Her main administrative contributions have been in the creation of world class teams. Each of these types of contributions is impressive and each is hard—I think it takes a unique person to be able to do both so well.

Today I want to talk about the notion of proof, with all its various meanings.

…And To Make A Long Story Short—

All: Too late! —from the 1985 movie “Clue”

Lane Hemaspaandra was among the youngest present at the creation of the Computational Complexity Conference (CCC). We should thank him and all those who promoted this great conference in the green days of our field—indeed we will. He is older now, as are we all, but continues to make important contributions to complexity theory.

Today Dick and I want to talk about an older idea from the kitchen of Lane and others, and how it adds mustard to ideas we have already discussed on this blog.