If $B-A=ww^{\top}$ for symmetric and orthogonal matrices $A$ and $B$, how to show that $w$ has two nonzero entries?

Solution 1:

Here is another approach. By the given conditions, $A$ and $B$ must be symmetric permutation matrices. Hence $Ae=Be=e$ where $e$ is the vector of ones. If $A-B=ww^T$ for some nonzero vector $w$, then $0=(A-B)e=ww^Te$. Therefore $w^Te=0$. However, as $A$ and $B$ are permutation matrices, the entries of $A-B$ are $0$ or $\pm1$. Therefore so are the entries of $w$. The equality $w^Te=0$ thus further implies that $w$ has the same number of $1$s as the number of $-1$s.

If $w$ has more than two nonzero elements, it must have at least two $1$s. By a reindexing, we may assume that $w=(1,1,-1,-1,\ast,\ldots,\ast)^T$. But then the leading principal $2\times2$ submatrix of $A-B$ will be $\pmatrix{1&1\\ 1&1}$, which is impossible because $A-B$ is a difference between two permutation matrices. Hence $w$ has exactly two nonzero elements and they are one $1$ and one $-1$.

Solution 2:

Here is a sketch of proof. Let $A$ be $n\times n$. Since $A$ and $B$ are symmetric orthogonal $\{0,1\}$-matrices and $A-B$ has rank one, we may assume that $$ A=\underbrace{R\oplus R\oplus\cdots\oplus R}_{m\text{ copies}}\oplus I_{n-2m} $$ where $R=\pmatrix{0&1\\ 1&0}$ and either $$ B=I_2\oplus\underbrace{R\oplus\cdots\oplus R}_{m-1\text{ copies}}\oplus I_{n-2m} $$ or $$ B=\underbrace{R\oplus R\oplus\cdots\oplus R}_{m+1\text{ copies}}\oplus I_{n-2(m+1)}. $$ In both cases, $A-B$ is similar via a permutation to $\pm\pmatrix{1&-1\\ -1&1}\oplus0$. Hence the result follows.