Prove that rank(A) = rank(A|C)

Question

I have a problem in which I am trying to prove over GF(2) that a binary symmetric matrix (A) with a diagonal of ones has a rank always equal to the rank of its augmented matrix with a ones vector (C) $$ C=\left[\begin{array} \\ 1 \\ \vdots \\ 1 \end{array}\right] $$

To clarify, such matrix is constructed like so: $$ A=\left[\begin{array}{rrrr} 1 & a_{1,1} & a_{1,2} & \dots & a_{1,n} \\ a_{1,1} & 1 & a_{2,1} & \ddots & \vdots \\ a_{1,2} & a_{2,1} & \ddots & a_{n-1,n-1} & a_{n-1,n} \\ \vdots & \ddots & a_{n-1,n-1} & 1 & a_{n,n} \\ a_{1,n} & \dots & a_{n-1,n} & a_{n,n} & 1 \end{array}\right] $$

For example, a 3 by 3 matrix like this has a rank of 2: $$ A=\left[\begin{array}{rrr} 1 & 1 & 0 \\ 1 & 1 & 0 \\ 0 & 0 & 1 \end{array}\right] $$ When we augment it with a ones vector, we get this matrix which also has a rank of 2: $$ A|C=\left[\begin{array}{rrr|r} 1 & 1 & 0 & 1 \\ 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \end{array}\right] $$ Cleary rank(A) = rank(A|C) over GF(2).

Why is this always true for such type of matrices?

If you have a proof, an idea, or a suggestion on how to proceed, please let me know. Any help is appreciated.

Answer 1

Let $e=(1,1,\ldots,1)^T$. When $A$ is a symmetric matrix over $GF(2)$ whose diagonal entries are all equal to $1$, $Ax=e$ is always solvable. Consequently, $A$ has the same rank as the augmented matrix $[A|e]$.

Since $A$ is a symmetric matrix with nonzero diagonal entries, the symmetric bilinear form it represents is non-alternate (i.e. $x^TAx$ is not always zero). It follows that $A$ can be diagonalised by congruence (cf. Irving Kaplansky, Linear Algebra and Geometry: a Second Course, p.23, theorem 20), i.e. $A=PDP^T$ for some invertible matrix $P$ and some diagonal matrix $D$. By permuting the rows and columns of $A$ if necessary, we may assume that $D=I_r\oplus0$, where $r$ is the rank of $A$. By assumption, all diagonal entries of $A$ are equal to $1$. Therefore, for each $i\in\{1,2,\ldots,n\}$, we have $$ 1=a_{ii}=\sum_{j=1}^rp_{ij}^2=\sum_{j=1}^rp_{ij}.\tag{1} $$ In vector form, this means $e=PDe$. It follows that when $x=(P^T)^{-1}e$, $$ Ax=PDP^T(P^T)^{-1}e=PDe=e. $$

Remarks.

1. Note that in $(1)$, we have $p_{ij}^2=p_{ij}$ because $p^2=p$ for $p=0,1$. This is the only place where we truly rely on the properties of $GF(2)$, and this suggests that $Ax=e$ may not be solvable over other fields. E.g. over $\mathbb R$, $$ A=\pmatrix{ 1&0&0&0&0&1\\ 0&1&0&0&0&1\\ 0&0&1&0&1&0\\ 0&0&0&1&1&0\\ 0&0&1&1&1&1\\ 1&1&0&0&1&1} $$ is singular (the sum of its first four columns is equal to the sum of its last two columns) but $[A|e]$ has rank $6$.
2. The argument in the answer above can be generalised to prove that the system of linear equations $$ a_{i1}x_1+a_{i2}x_2\cdots+a_{in}x_n=a_{ii},\quad i=1,\cdots,n $$ is always solvable over $GF(2)$ when $A$ is symmetric. See Jyrki Lahtonen's answer for details.

Answer 2

I have a proof, which I don't like too much, but still is a proof.

Rank$(A)=$rank$(A|C)$ if and only if column $C$ is a linear combination of columns of A.

We proceed by induction on $n$ the number of columns of $A$.

For $n=1$ there is nothing to prove.

Suppose the claim is true for any $m<n$ and let $A$ be a symmetric matrix with $1$ on the diagonal. Let $A_i$ be the matrix obtained by removing the $i^{th}$ row and $i^{th}$ column. By induction the vector $(1,\dots,1)^T$ is a combination of the columns of $A_i$.

In other words, there exists a linear combination of the columns of (the full) $A$ so that the result is $(1,1,\dots,x,1,1,\dots,1)^T$ with a value $x$ at the place $i$, which can be $0$ or $1$. If $x=1$ then we obtained $(1,\dots,1)^T=C$ and we are done. Otherwise, the result is $(1,\dots,1,0,1,\dots,1)^T$ with $0$ at place $i$.

By applying this argument for every $i$, either we obtain $C$ as a linear combination of columns of $A$, and in this case we are done, or for every $i$ we obtain the vector with all $1$ except $0$ at place $i$. Therefore, the rank of $A$ equals the rank of $(A|B)$ where $B$ is the matrix $\left(\begin{array}{cccccc}0&1&1&\dots&1\\1&0&1&\dots&1\\\vdots&\vdots &\vdots &\vdots& \\1&1&1&\dots&0\end{array}\right)$.

By summing the first column of $B$ to the other columns of $B$ we obtain the matrix $B^1=\left(\begin{array}{ccccccc}0&1&1&1&\dots&1\\1&1&0&0&\dots&0\\1&0&1&0&\dots&0\\ 1&0&0&1&\dots&0\\ \vdots&\vdots &\vdots &\vdots&\vdots&\vdots& \\1&0&0&0&\dots&1\end{array}\right)$

So rank$(A)=$rank$(A|B)=$rank$(A|B^1)$.

Now, if $n$ is even, then by summing all the columns of $B^1$ we obtains $E_1=(1,0,0,\dots,0)^T$. Therefore rank$(A)=$rank$(A|B)=$rank$(A|B^1)=$rank$(A|B^1|E^1)$.

It is now immediate that rank$(B^1|E^1)=n$ so $A$ has full rank and we are done.

Hence we are left to the case where $n$ is odd.

Now, let $A^1=(1,a_{1,2},\dots,a_{1,n})^T$ be the first column of $A$. Suppose that the number of $i\geq 2$ so that $a_{1,i}=1$ is even (in other words suppose that the total number of $1$'s appering in $A^1$ is odd). In this case By summing to $A^1$ the columns of $B^1$ corresponding to places where $a_{1,i}=1$ we obtain the column $E_1=(1,0,\dots,0)^T$. Therefore, as above rank$(A)=$rank$(A|B)=$rank$(A|B^1)=$rank$(A|B^1|E^1)=n$ and we are done.

It follows that if $A$ has not full rank, then the total number of $1$'s appearing in $A^1$ is even.

Since this argument applies to all columns of $A$, we have that if $A$ has not full rank, than any column has an even number of $1$'s. It follows that the total number of $1$'s appearing on $A$ is even. But $A$ is symmetric, so its $1$'s are distributed on the dyagonal (where by hypothesis we have exactly $n$ $1$'s) plus an even number $2N$ eslewhere. But this is impossible because we are in the case where $n$ is odd, so $n+2N$ is odd.

I suspect that one can find a clean proof of few lines.