Redundant Systems

• Even though a matrix is singular, it may still have a solution. Consider again the same singular matrix:
  
  $$A=\left[ \begin{array}{rrr} 1 & -2 & 3 \\ 2 & 4 &-1 \\ -1 &-14 & 11\\ \end{array} \right]$$
  
  
  Suppose we solve the system $Ax = b$ where the right-hand side is $b = [5, 7, 1]^T$.

  >> lu ( Ab )
  ans =
   2.0000      4.0000     -1.0000    	7.0000
  -0.5000    -12.0000     10.5000			4.5000
   0.5000      0.3333      0					0
  

  and the back-substitution cannot be done.
  • The output suggests that $x_3$ can have any value.
  • Suppose we set it equal to 0. We can solve the first two equations with that substitution, that gives $[17/4, -3/8, 0]^T$.
  • Suppose we set $x_3$ to 1 and repeat. This gives $[3, 1/2, 1]^T$, and this is another solution.
  • We have found a solution, actually, an infinity of them. The reason for this is that the system is redundant.
• What we have here is not truly three linear equations but only two independent ones. The system is called redundant.
• Here is a comparison of singular and nonsingular matrices:
  

  Table 1: A comparison of singular and nonsingular matrices

  For Singular matrix A:	For Nonsingular Matrix A:
  It has no inverse, $A^{-1}$	It has an inverse, $A^{-1}$
  Its determinant is zero	The determinant is nonzero
  There is no unique solution	There is a unique solution
  to the system $Ax = b$	to the system $Ax = b$
  Gaussian elimination cannot avoid	Gaussian elimination does not
  a zero on the diagonal	encounter a zero on the diagonal
  The rank is less than $n$	The rank equals $n$
  Rows are linearly dependent	Rows are linearly independent
  Columns are linearly dependent	Columns are linearly independent