Putnam 2019, Problem B-3

Let \(Q\) be an \(n\)-by-\(n\) real orthogonal matrix, and let \(u \in \mathbb{R}^n\) be a unit column vector (that is, \(u^T u = 1\)). Let \(P = I - 2uu^T\), where \(I\) is the \(n\)-by-\(n\) identity matrix. Show that if \(1\) is not an eigenvalue of \(Q\), then \(1\) is an eigenvalue of \(PQ\).

Solution:
**Solution 1.** We first note that $P$ corresponds to the linear transformation on $\mathbb{R}^n$ given by reflection in the hyperplane perpendicular to $u$: $P(u) = -u$, and for any $v$ with $\langle u,v \rangle = 0$, $P(v) = v$. In particular, $P$ is an orthogonal matrix of determinant $-1$.

We next claim that if $Q$ is an $n \times n$ orthogonal matrix that does not have 1 as an eigenvalue, then $\det Q = (-1)^n$. To see this, recall that the roots of the characteristic polynomial $p(t) = \det(tI - Q)$ all lie on the unit circle in $\mathbb{C}$, and all non-real roots occur in conjugate pairs ($p(t)$ has real coefficients, and orthogonality implies that $p(t) = \pm t^n p(t^{-1})$). The product of each conjugate pair of roots is 1; thus $\det Q = (-1)^k$ where $k$ is the multiplicity of $-1$ as a root of $p(t)$. Since 1 is not a root and all other roots appear in conjugate pairs, $k$ and $n$ have the same parity, and so $\det Q = (-1)^n$.

Finally, if neither of the orthogonal matrices $Q$ nor $PQ$ has 1 as an eigenvalue, then $\det Q = \det(PQ) = (-1)^n$, contradicting the fact that $\det P = -1$. The result follows.

**Remark.** It can be shown that any $n \times n$ orthogonal matrix $Q$ can be written as a product of at most $n$ hyperplane reflections (Householder matrices). If equality occurs, then $\det(Q) = (-1)^n$; if equality does not occur, then $Q$ has 1 as an eigenvalue. Consequently, equality fails for one of $Q$ and $PQ$, and that matrix has 1 as an eigenvalue.

**Solution 2.** This solution uses the (reverse) Cayley transform: if $Q$ is an orthogonal matrix not having 1 as an eigenvalue, then
$$A = (I-Q)(I+Q)^{-1}$$
is a skew-symmetric matrix (that is, $A^T = -A$).

Suppose then that $Q$ does not have 1 as an eigenvalue. Let $V$ be the orthogonal complement of $u$ in $\mathbb{R}^n$. On one hand, for $v \in V$,
$$(I-Q)^{-1}(I-QP)v = (I-Q)^{-1}(I-Q)v = v.$$

On the other hand,
$$(I-Q)^{-1}(I-QP)u = (I-Q)^{-1}(I+Q)u = Au$$
and $\langle u,Au \rangle = \langle A^T u,u \rangle = \langle -Au,u \rangle$, so $Au \in V$. Put $w = (1-A)u$; then $(1-QP)w = 0$, so $QP$ has 1 as an eigenvalue, and the same for $PQ$ because $PQ$ and $QP$ have the same characteristic polynomial.

**Remark.** The Cayley transform is the following construction: if $A$ is a skew-symmetric matrix, then $I+A$ is invertible and
$$Q = (I-A)(I+A)^{-1}$$
is an orthogonal matrix.

**Remark.** (by Steven Klee) A related argument is to compute $\det(PQ-I)$ using the matrix determinant lemma: if $A$ is an invertible $n \times n$ matrix and $v,w$ are $1 \times n$ column vectors, then
$$\det(A + vw^T) = \det(A)(1 + w^T A^{-1} v).$$

This reduces to the case $A = I$, in which case it again comes down to the fact that the product of two square matrices (in this case, obtained from $v$ and $w$ by padding with zeroes) retains the same characteristic polynomial when the factors are reversed.