in collaboration with guest contributor Gabriel Coutinho
My frequent collaborator Gabriel Coutinho and I have very different problem solving styles. In his own words, “we could write a book together; your part will have fancy group theory and nice drawings and mine will have sloppy proofs of eigenvalue bounds.” We challenged each other to this problem, which is B3 from the 2019 Putnam Math Competition. There was struggle and despair, but the next morning, we came up with two very different solutions.
The Problem:
Let \(Q\) be an \(n\times n\) real orthogonal matrix and let \(u\) be a \(n\)-dimensional real (column) unit vector. Let \(P = I – 2u u^T\), where \(I\) is the \(n\times n\) identity matrix. Show that if \(1\) is not an eigenvalue of \(Q\), then \(1\) is an eigenvalue of \(PQ\).
Note that \(P\) is a reflection; it is an involution and also called a Householder transformation
Krystal’s solution: what exactly does \(P\) do?
We can easily see that \(P\) sends \(u\) to \(-u\) and fixes everything orthogonal to \(u\). But we can actually prescribe the behaviour of a reflection.
Lemma. If \(x\) and \(y\) are real unit vectors and $$P = I – 2\frac{(x-y)(x-y)^T}{\langle x-y, x-y \rangle},$$ then \(Px = y\).
Proof. We observe the following \[ \begin{split} Px &= x – 2\frac{(x-y)(x-y)^Tx}{\langle x-y, x-y \rangle} \\ &= x – 2\frac{(x-y)(x^Tx-y^Tx)}{x^Tx- x^Ty -y^Tx+ y^Ty} \\ &= x – 2\frac{(x-y)(1-y^Tx)}{2(1 – y^Tx)} \\ &= x – (x-y) \\ &= y, \end{split} \] as claimed. ∎
Corollary. Suppose \(u\) is a unit vector such that \( u = x – y \) where \( |x| = |y| =\alpha \). If \(P = I – 2u u^T\), then \(P \left( \frac{x}{\alpha} \right) = \frac{y}{\alpha} \).
Proof. We observe that \(\frac{x}{\alpha}\) and \(\frac{y}{\alpha}\) are unit vectors. The corollary now follows from the Lemma. ∎
To solve the problem, we observe that \(Q\) and \(Q^T\) have the same eigenvalues and so, if \(1\) is not an eigenvalue of \(Q\), there exists a matrix \(M = (I-Q^T)^{-1}\). Let \(x = Mu\). We see that \[u = (I-Q^T)x = x – Q^Tx.\] Since \(Q^T\) is an orthogonal matrix and thus preserves lengths, we have that \(|x| = |Q^Tx|\). Let \(x’ = \frac{x}{|x|}\). We may now apply the corollary and conclude that \(P\) takes \(x’ \) to \(Q^Tx’\).
Now we see that \[PQ (Q^Tx’) = Px’ = Q^Tx’\] and so \(Q^Tx’\) is an eigenvector for \(PQ\) with eigenvalue \(1\).
Gabriel’s solution: let’s go with some determinants
Let \(R\) any real orthogonal matrix. Its determinant is \(\pm 1\) and all of its eigenvalues have norm 1. The \(P\) a reflection about an \((n-1)\)-dimensional subspace; it has one eigenvalue equal to \(-1\) and all other eigenvalues are \(1\) and so \(\det P = -1\). The idea is to show if \(\det(Q) = (-1)^{n-1}\), then \(Q\) has \(1\) as an eigenvalue.
\(n\) is odd. Suppose \(R\) is an \(n\times n\) orthogonal matrix and \(\det(R) = 1\). Then \[ \det(I-R) = \det(R^T) \det(I-R) = \det(R^T – I) = (-1)^n \det(I-R). \] Since \(n\) is odd, we get that \(\det(I-R) = 0\), and \(1\) is an eigenvalue. Thus if \(Q\) has odd order, it must be that \(\det Q = -1\). As \(\det P = -1\), we have \(\det (PQ) = 1\) and the result follows.
\(n\) is even. Suppose \(\det(R) = -1\). Each complex eigenvalue comes with its complex conjugate, so there are an even number of complex eigenvalues and their product is \(1\). Then there must an odd number of eigenvalues equal to \(-1\). But then there is also an eigenvalue equal to \(1\), as there are an even number of eigenvalues in total. Thus if \(Q\) and \(P\) have even order, it must be that \(\det Q = 1\). As \(\det P = -1\), we have \(\det (PQ) = -1\) and the result follows.
Addendum
Gabriel later realized that both parts of his proof could be extended to the other parity and leaves it as an exercise to the avid reader.