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.
from Hot Weekly Questions - Mathematics Stack Exchange
Post a Comment