I need hep with the following problem.

We will work only in $\mathbb{F}_2$. Let say $A$ is a symmetric matrix with its main diagonal consisting of only $1$s. I need to prove that $1$ (the vector with all ones) is in the column space (or row-space as is symmetric) of $A$.

Any help is appreciated, thanks.

  • 1
    $\begingroup$ Can you write the vector all 1's as a combination of the two columns of $\mathbf{A}$?. $\endgroup$ – Sudarsan Dec 3 '13 at 19:36
  • $\begingroup$ @Sudarsan Why? Consider $A=I_n$ with $n\ge3$. $\endgroup$ – user1551 Dec 4 '13 at 1:32

Let's say $A$ is $n\times n$. As it is symmetric, it can be decomposed into the form of $X^\top X$ for some $m\times n$ matrix $X$ with full row rank (i.e. rank $m$). Since $X$ has full rank and $m\le n$, as a linear operator, $X$ is onto. Hence there exists a vector $u$ such that $Xu=\mathbf1_m$, the all-one vector. However, as all diagonal entries of $A$ are equal to $1$, every column of $X$ must have odd parity. Therefore $X^\top\mathbf1_m=\mathbf1_n$ and in turn, $Au=X^\top Xu=\mathbf1_n$.

  • $\begingroup$ Thanks. One question, what is the theorem for the $X^T X$ decomposition, or how can I prove that? $\endgroup$ – MikeSB Dec 4 '13 at 4:09
  • $\begingroup$ @MikeSB This follows from the fact that every symmetric bilinear form over a field is diagonalisable (proofs of this fact can be easily found online). Now suppose $A=Y^\top DY$ is a diagonalisation (where $Y$ is invertible and $D$ is diagonal). By reindexing the rows and columns, we may assume that the diagonal entries of $D$ have some $m$ leading ones and $n\times m$ trailing zeros. Then $A$ has rank $m$. Take the first $m$ rows of $Y$ to form $X$, we get $A=X^\top X$. Since $Y$ is invertible, it has linearly independent rows and hence $X$ has full rank. $\endgroup$ – user1551 Dec 4 '13 at 5:00

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.