# Maximum number of linearly dependent columns of a $m \times n$ matrix

Question statement : True or false ? If $$A$$ is a ($$4 \times 8$$) matrix, then any six columns are linearly dependent. Textbook answer : True.

I can't understand the reasoning behind this. From my perspective , for such matrix there are at most 4 pivot columns, therefore at most 4 linearly independent columns, which would imply there are at most 4 linearly dependent columns ?

I don't know where to begin, help would be appreciated.

• You are right that the size of an independent set of columns is at most 4. Since each set of columns is either dependent or independent, what does that say about a set of more than 4 columns? – Guus B Dec 4 '19 at 15:49

Your attempt is almost there: ...therefore at most 4 linearly independent columns, therefore any six columns must be linearly dependent.

The proper way to state this is that the rank of an $$n\times m$$ matrix is at most $$\min(m,n)$$, therefore your matrix has rank at most $$4$$, therefore any $$5$$ or more rows (respectively, columns) must be linearly dependent.

• Awesome, I think I understand now. So for this specific matrix, any set of at lest 5 and at most $m$ columns will be automatically dependent, is that right ? Similarly, any set of rows of at most $n$ rows will be linearly independent ? – hexaquark Dec 4 '19 at 15:56
• @hitechphysics Yes. No. You can replace columns by rows in your first sentence, and $m$ by $n$, to get the correct formulation. – Arnaud Mortier Dec 4 '19 at 16:06
• @hitechphysics But note that it is not necessary to write explicitly "at most $m$ columns", since there are no more than $m$ columns anyway. – Arnaud Mortier Dec 4 '19 at 16:07

From my perspective , for such matrix there are at most 4 pivot columns, therefore at most 4 linearly independent columns, which would imply there are at most 4 linearly dependent columns ?

You are right about the maximum number of pivot columns and therefore the maximum number of linearly independent columns, but what makes you think the italic statement follows from that?

Take a look at:

$$\begin{pmatrix} \color{blue}{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & \color{blue}{1} & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & \color{blue}{1} & \color{red}{2} & \color{red}{3} & \color{red}{4} & \color{red}{5} & \color{red}{6} \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \end{pmatrix}$$

• How many pivot columns are there?
• What is the maximum number of linearly independent columns you can pick?
• What is the maximum number of linearly dependent columns you can pick?
• Thank you for you answer. There are 3 pivot columns, the maximum number of independent columns is 4 and the maximum number of linearly dependent columns 8 ! Is that right ? – hexaquark Dec 4 '19 at 16:23
• Correct (that is: maximally 4 in general, 3 in this particular example; similar for the dependent ones). You can now probably see how this generalises to the $m\times n$-case. – StackTD Dec 4 '19 at 16:32