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


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

  • $\begingroup$ 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 $$ $\endgroup$ – Gabriel Romon Aug 13 at 8:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.