Mathematics

Underdetermined Systems

Underdetermined linear systems involve more unknowns than equations. When they are accompanied by additional constraints, they are the purview of linear programming. By itself, the backslash operator deals only with the unconstrained system. The solution is never unique. MATLAB finds a basic solution, which has at most m nonzero components, but even this may not be unique. The particular solution actually computed is determined by the QR factorization with column pivoting (see a later section on the QR factorization).

Here is a small, random example.

• R = fix(10*rand(2,4))
  
  R =
         6     8     7     3
         3     5     4     1
  
  b = fix(10*rand(2,1))
  b =
         1
         2
  

The linear system Rx = b involves two equations in four unknowns. Since the coefficient matrix contains small integers, it is appropriate to use the format command to display the solution in rational format. The particular solution is obtained with

• format rat
  p = R\b
  p =
        0 
       5/7
        0 
     -11/7
  

One of the nonzero components is p(2) because R(:,2) is the column of R with largest norm. The other nonzero component is p(4) because R(:,4) dominates after R(:,2) is eliminated.

The complete solution to the underdetermined system can be characterized by adding an arbitrary vector from the null space, which can be found using the null function with an option requesting a "rational" basis.

• Z = null(R,'r')
  Z =
        -1/2         -7/6     
        -1/2          1/2     
          1            0      
          0            1
  

It can be confirmed that R*Z is zero and that any vector x where

• x = p + Z*q
  

for an arbitrary vector q satisfies R*x = b.

Overdetermined Systems

Inverses and Determinants