Transforming overdetermined system of equations to normal system of equations

Question

Consider the following overdetermined linear system

$$Ax=b$$

where $A$ is a given tall $n \times k$ matrix ($n>k$), $x$ is a $k$-vector of unknowns, and $b$ is a given $n$-vector. Suppose further that matrix $A$ has full column rank, i.e., $\mbox{rank} (A)=k$. Is it legitimate to delete linearly dependent rows?

If so, then we obtain another system of linear equations which has the same number of equations as the number of unknowns. Hence, the conclusion is that any overdetermined system of linear equations can be transformed to one where the number of equations is equal to the number of unknowns. Where is the problem in my reasoning? Please guide me!

Answer 1

Your reasoning is fine as long as your system is consistent (i.e. has a solution). There is just one thing to consider: Some people also write inconsistent overdetermined systems that way - that are systems that have no solution. This might result in different solutions depending on which rows you remove.

Answer 2

Consider the following example $(n=3,\,k=2)$ $$\eqalign{ A=\pmatrix{1&4\\2&5\\2&6},\quad b=\pmatrix{12\\13\\14},\quad{\rm rank}(A)=2 \\ }$$ Technically, any of the three rows of $A$ is a linear combination of other two.
For example, you can write the third row as $$\eqalign{ \pmatrix{2&6} = \tfrac{2}{3}\pmatrix{1&4} + \tfrac{2}{3}\pmatrix{2&5} }$$ The concept of linear dependence isn't enough, because it doesn't tell you which row to eliminate.
Eliminating the first, second, or third row will yield three completely different answers $$\eqalign{ x_1 &= \pmatrix{4\\1} , \quad x_2 &= \pmatrix{-8\\\;\;5} , \quad x_3 &= \pmatrix{-8/3\\\;11/3} }$$ What you should really do in this situation is calculate the least-squares solution using all of the rows. $$\eqalign{ x_L &= \pmatrix{-40/17\\\;\;57/17} }$$

Answer 3

Whether it is a consistent or inconsistent system of equations, if you want to use analytical methods, you can delete any dependent row which you can establish to be a valid linear combination of any subset of the other undeleted rows. However you must also join the left hand side values as a column of your matrix with value: -b. Otherwise you will struggle with inconsistent results in your calculation. The negation of that column is essential.

Special Note: make sure you do your row deletions, only one row at a time. If you delete more than one row at a time, you will inadvertently delete a linearly essential row. Guassian reduction remains the best way to identify such rows even when N > M. It also exposes the row which will never combine with any set of the rest, or the cause of the inconsistency, if the system is inconsistent.