# Determine that a vector is in the column space of a matrix

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.

• Can you write the vector all 1's as a combination of the two columns of $\mathbf{A}$?. – Sudarsan Dec 3 '13 at 19:36
• @Sudarsan Why? Consider $A=I_n$ with $n\ge3$. – 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$.
• Thanks. One question, what is the theorem for the $X^T X$ decomposition, or how can I prove that? – MikeSB Dec 4 '13 at 4:09
• @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. – user1551 Dec 4 '13 at 5:00