Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer
    
I got it, thanks! –  Elena Jun 9 '12 at 12:14
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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