# If $A\in {\mathbf F_2}^{n\times n}$ is symmetric, its diagonal is in the span of its columns

Let $$A$$ be an $$n\times n$$ symmetric matrix with entries in $$\mathbf F_2$$ (the field with 2 elements, also referred to as $$\mathbb Z/2\mathbb Z$$). Prove that the diagonal of $$A$$ is in the span of its columns.

If the diagonal is only zeros the problem is trivial, but I haven't made any significant progress in the general case...

## 1 Answer

Consider the natural bilinear form $$\cdot$$ on $$\mathbb{F}_2^n$$.

Note that for all $$v,w \in \mathbb{F}_2^n$$, $$(Av) \cdot w = (Aw) \cdot v$$.

As a consequence, if $$R$$ is the range of $$A$$ and $$K$$ is the kernel of $$A$$, $$R^{\perp} \subset K$$. Since $$\dim\,R^{\perp}=n-\dim\,R=\dim\,K$$, $$R^{\perp}=K$$.

Note that this implies that $$K^{\perp}=(R^{\perp})^{\perp} = R$$ (for the second equality, the dimension equality is easy and one inclusion also is).

So what you need to show is that the diagonal (denoted $$d$$) of $$A$$ is orthogonal to any vector of $$K$$.

Now, if $$Ax=0$$, then $$x^TAx=0$$, and, since we work in $$\mathbb{F}_2^n$$, $$x^TAx$$ is $$d \cdot x$$.

• Thanks for your answer. You could argue more directly that in general $\text{Im }A = (\text{ker }A^T)^\perp$ and since $A$ is symmetric this yields $\text{Im }A =(\text{ker }A)^\perp$. Also, fleshing out the details of the final step: $$x^TAx = \sum_{ij} A_{ij} x_i x_j = \sum_i A_{ii} x_i^2 + 2\sum_{i< j} A_{ij} x_i x_j = \sum_i A_{ii} x_i$$ – Gabriel Romon Aug 13 at 8:16