Prove that rank(A) = rank(A|C) 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.
 A: 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.

*

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

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

A: 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.
