# Spanning a vector with no zero coordinates

Given a complex square matrix with 1-s on the main diagonal (and arbitrary values elsewhere), do its columns span a vector with no zero coordinate?

Clarification: What I'm asking is, given a complex matrix with 1-s on the main diagonal (and arbitrary values elsewhere), does its column space necessarily contain a vector in which each component is nonzero? Ofcourse, I know not all vectors in the column space are like that, I'm just asking if there is one.

-
What does it mean for a collection of vectors to "span" a vector? – Chris Eagle Jun 9 '12 at 11:58
I would interpret the question to be asking whether the column space necessarily contains a vector with no zero components. – Gerry Myerson Jun 9 '12 at 11:59
@GerryMyerson: Yes, you interpret in accordance to what I meant. – Elena Jun 9 '12 at 12:03

One (final) edit, down toward the bottom.

Take any vector $v$ in the column space. Suppose it has $m$ zeros in it. Take a column that has its diagonal 1 in one of the slots where $v$ has a zero. Adding any non-zero multiple of it to $v$ will create a vector with a non-zero entry in that slot, and there are only finitely many multiples you have to avoid so as not to make any new zeros. So you have reduced the number of zeros by one. Proceed by induction.

This proof fails over a field of non-zero characteristic.

EDIT: It's not just the proof that fails in positive characteristic, it's the result, at least in one case. Over the field of two elements, the matrix $$\pmatrix{1&0&1\cr1&1&0\cr0&1&1\cr}$$ satisfies the hypotheses, but its column space is just $$\lbrace(0,0,0),(1,1,0),(0,1,1),(1,0,1)\rbrace$$ I expect there are examples of other sizes and over other fields but I haven't found them yet.

MORE EDIT: It's cardinality, not characteristic, that matters. The proof in the first paragraph works over any infinite field; there are counterexamples over any finite field. Over the field of 3 elements: $$\pmatrix{1&2&2&0\cr0&1&2&2\cr1&0&1&2\cr1&1&0&1\cr}$$ Over the field of 5 elements, I haven't found any with so much symmetry [but see final edit, below], but here's one just to show it can be done: $$\pmatrix{1&4&4&4&4&0\cr0&1&2&4&3&3\cr1&0&1&3&2&3\cr1&2&0&1&3&4\cr1&3&2&0&1&2\cr1&1&3&0&2&1\cr}$$ Given a field of $q$ elements, here's how to construct a square matrix of order $q+1$ with ones down the diagonal, such that every element of the column space has a zero component:

Let the first column be $v=(1,1,\dots,1,0)$. Let the second column be $w=(0,1,a_1,a_2,a_3,\dots,a_r)$ where $1,a_1,\dots,a_{r-1}$ is any enumeration of the non-zero elements of the field (so $r=q-1$). Now for $k=3,4,\dots,q+1$ let column $k$ be the unique linear combination of $v$ and $w$ that has entry $k$ equal to 1 and entry $k-1$ equal to zero.

FINAL EDIT. Here's a solution for $q=5$ with the kind of symmetry I was hoping for. I reckon this solution makes it clear what to do for any prime $q$, perhaps for any $q$. $$\pmatrix{1&0&4&3&2&1\cr1&1&0&4&3&2\cr1&2&1&0&4&3\cr1&3&2&1&0&4\cr1&4&3&2&1&0\cr0&1&1&1&1&1\cr}$$

-
I got it, thanks! – Elena Jun 9 '12 at 12:14

No. For example take $A=\binom{1\hspace{3pt}0}{0\hspace{3pt}1}$. Then the vector space spanned by its columns is $\mathbb{R}^2$, in particular $\binom{0}{1}$ and $\binom{1}{0}$ are there.
Moreover, a vector space with no zero coordinate in its vectors is $1$-dimensional, since if there are at least two linearly independant vectors then we will be able to find a linear combination of them with zero at any coordinate we like.

-
I should have been more clear. I'm not asking whether all vectors are like that, but rather, is there a vector in the column space with no zero component. – Elena Jun 9 '12 at 12:02
I think that Elena asks for a single vector. – Mohamed Jun 9 '12 at 12:06