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

Question

Suppose that $A$ and $B$ are binary square matrices of same dimension and that $A=A^{\top}=A^{-1}$ (same for $B$), i.e. they are symmetric and orthogonal. In addition, suppose $\text{rank}(B-A)=1$ so that $B-A=uv^{\top}$ for nonzero vectors $u$ and $v$. I want to show that $B-A$ has the form $ww^{\top}$, where $w$ is a column vector with only two nonzero entries whose values are $\pm 1$.

Since $B-A$ is symmetric (can be easily verified), then $B-A=ww^{\top}$ for some nonzero vector $w$. I know this part follows because the row space and column space of $B-A$ are the same, but I didn't think yet how to prove it rigorously. Since $w$ is nonzero, some entry of $w$, say $w_i$, is not zero. Now, let $e_i$ be a column vector such that the $i$-th entry is $1$ and is the only nonzero entry. Then: $$ e_i^{\top}(B-A)e_i=e_i^{\top}(ww^{\top})e_i=(e_i^{\top}w)(w^{\top}e_i)=w_i^2, $$ where $w_i$ is the $i$-th nonzero entry of $w$. Since the entries of $B-A$ are in $\{-1,0,1\}$ because $A$ and $B$ are binary and $w_i \neq 0$, then $w_i^2=1$, which implies $w_i=\pm 1$.

With the above reasoning, I know that the nonzero entries of $w$ are either $-1$ or $1$. Now, I just need to figure out how to prove that there are only two of these nonzero entries. If I could show that $w^{\top}w=2$, I'd know that there are only two nonzero entries, although I'd not be able to tell their sign. But it'd be a start.

I don't expect to get a complete solution from you (although this'd be nice). I just need some insight from more experienced people in linear algebra to go forward. Would you be able to give me some directions to follow? Maybe some properties of $B-A$ that I'm not seeing?

Answer 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$.

Answer 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.