Let $A\in (\mathbb{Z}_2)^{n\times n}$ be a symmetric matrix. Let $Row(A)$ denote its rowspace.
Prove that $$(a_{1,1}, a_{2,2},\cdots, a_{n,n}) \in Row(A)$$
I tried induction on $n$. If a row is completely empty we can remove the row and corresponding column. If $rank A=n$ we are also trivially done. Thus I tried doing some row operations and column operations of the form $r_i\rightarrow r_i-r_j, c_i\rightarrow c_i-c_j$ at the same time, which didn't work because I want to keep symmetry which also changes the rows.
I thought there might be a more combinatorial/graph theory solution.
Best Answer
We proceed by induction on $n$. We use the inductive hypothesis to its fullest potential:
If I remove row $i$ and column $i$, then the statement is true by IH. Hence there exists $x_1, \cdots, x_{i-1}, x_{i+1}, \cdots, x_n$ such that $\sum x_ir_i = (a_{11}, a_{22}, \cdots, a_{i-1,i-1}, T, a_{i+1,i+1}, \cdots, a_{nn})$ where $r_i$ is the $i$th row vector of $A$.
If $T=a_{i,i}$ we are done. Otherwise, we get $V-e_i$ where $V=(a_{11}, \cdots, a_{nn})$ and $e_i=(\underbrace{0,\cdots,0}_{i-1}, 1, \underbrace{0,\cdots,0}_{n-i})$. We can do this to every $1\le i\le n$.
This means we can get $e_i+e_j$ and all vectors in the orthogonal component of $1_n$ (ie all vectors with an even number of 1's). Furthermore, if a row vector has an odd number of 1's, then the rank of $A$ is $n$ (ie all vectors are okay). If $V$ has an even number of 1's, I'm done. Otherwise, $V$ has an odd number of 1's and every row of $A$ must have an even number of $1$'s, which implies $A$ has an even number of $1$'s. But since $A$ is symmetric, the number of 1's in $A$ has the same parity as the number of 1's in $V$, absurd!