Some Facts About Linear Systems

Section 2.3 Some Facts About Linear Systems

Subsection 2.3.1 Some inconvenient truths

In the last section we learned how to solve a linear system using MATLAB. Input the following:

>> A = ones(4,4)
>> b = randn(4,1)
>> x = A  b

🔗

As you will find, there is no solution to the equation \(A \xb = \bb\text{.}\) This unfortunate circumstance is mostly the fault of the matrix, \(A\text{,}\) which is too simple, its columns (and rows) are all the same. Now try

>> b = ones(4,1)
>> x = [ 1 0 0 0]'
>> A*x

So the system \(A \xb = \bb\) does have a solution. Still unfortunately, that is not the only solution. Try

>> x = [ 0 1 0 0]'
>> A*x

We see that this \(x\) is also a solution. Next try

>> x = [ -4 5 2.27 -2.27]'
>> A*x

This \(x\) is a solution! It is not hard to see that there are endless possibilities for solutions of this equation.

🔗

Subsection 2.3.2 Basic theory

The most basic theoretical fact about linear systems is

🔗

Theorem 2.3.1.

A linear system \(A\xb = \bb\) may have 0, 1, or infinitely many solutions.

🔗

In most (but not all!) engineering applications we would want to have exactly one solution. The following two theorems tell us exactly when we can and cannot expect this.

🔗

Theorem 2.3.2.

Suppose \(A\) is a square (\(n \times n\)) matrix. The following are all equivalent:

The equation \(A\xb = \bb\) has exactly one solution for any \(\bb\text{.}\)
🔗

🔗
\(det(A) \ne 0\text{.}\)
🔗

🔗
\(A\) has an inverse.
🔗

🔗
The only solution of \(A\xb = \mathbf{0}\) is \(\xb = \mathbf{0}\text{.}\)
🔗

🔗
The columns of \(A\) are linearly independent (as vectors).
🔗

🔗
The rows of \(A\) are linearly independent.
🔗

🔗

If \(A\) has these properties then it is called non-singular.

🔗

On the other hand, a matrix that does not have these properties is called singular.

🔗

Theorem 2.3.3.

Suppose \(A\) is a square matrix. The following are all equivalent:

The equation \(A\xb = \bb\) has 0 or \(\infty\) many solutions depending on \(\bb\text{.}\)
🔗

🔗
\(\det(A) = 0\text{.}\)
🔗

🔗
\(A\) does not have an inverse.
🔗

🔗
The equation \(A\xb = \mathbf{0}\) has solutions other than \(\xb = \mathbf{0}\text{.}\)
🔗

🔗
The columns of \(A\) are linearly dependent as vectors.
🔗

🔗
The rows of \(A\) are linearly dependent.
🔗

🔗

🔗

To see how the two theorems work, define two matrices (type in A1 then scroll up and modify to make A2) :

\begin{equation*} \verb&A1& = \left(\begin{array}{ccc}1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9\end{array}\right), \qquad \verb&A2& = \left(\begin{array}{ccc}1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 8\end{array}\right)\text{,} \end{equation*}

and two vectors:

\begin{equation*} \verb&b1& = \left(\begin{array}{c}0 \\ 3 \\ 6\end{array}\right), \qquad \verb&b2& = \left(\begin{array}{c}1 \\ 3 \\ 6\end{array}\right)\text{.} \end{equation*}

First calculate the determinants of the matrices:

>> det(A1)
>> det(A2)

Then attempt to find the inverses:

>> inv(A1)
>> inv(A2)

Which matrix is singular and which is non-singular? Finally, attempt to solve all the possible equations \(A \xb = \bb\text{:}\)

>> x = A1 \ b1
>> x = A1 \ b2
>> x = A2 \ b1
>> x = A2 \ b2

As you can see, equations involving the non-singular matrix have one and only one solution, but equation involving a singular matrix are more complicated.

🔗

Subsection 2.3.3 The Residual

Recall that the residual for an approximate solution \(x\) of an equation \(f(x) =0\) is defined as \(r = \|f(x)\|\text{.}\) It is a measure of how close the equation is to being satisfied. For a linear system of equations we define the residual vector of an approximate solution \(\xb\) by

\begin{equation*} \rb = A \xb - \bb\text{.} \end{equation*}

If the solution vector \(\xb\) were exactly correct, then \(\rb\) would be exactly the zero vector. The size (norm) of \(\rb\) is an indication of how close we have come to solving \(A \xb = \bb\text{.}\) We will refer to this number as the scalar residual or just the residual of the approximation solution:

\begin{equation*} r = \| A \xb - \bb \|\text{.} \end{equation*}

🔗

Exercises 2.3.4 Exercises

1.

By hand, find all the solutions (if any) of the following linear system using the augmented matrix and Gaussian elimination (following exactly the algorithm in the notes):

\begin{equation*} \begin{split}x_{1} + 2 x_{2} + 3 x_{3}&= 4, \\ 4 x_{1} + 5 x_{2} + 6 x_{3}&= 10, \\ 7 x_{1} + 8 x_{2} + 9 x_{3}&= 14 \,.\end{split} \end{equation*}

Try solving this system in MATLAB using the command x = A \ b. What happens? Turn in your hand work.

🔗

2.

Write a well-commented MATLAB function program mysolvecheck with input a number n that makes a random \(n \times n\) matrix \(A\) and a random vector \(\bb\text{,}\) solves the linear system \(A \xb = \bb\text{,}\) calculates the scalar residual \(r = \|A \xb - \bb\|\text{,}\) and outputs that number as \(r\text{.}\)
🔗

🔗
Write a well-commented MATLAB script program that calls mysolvecheck 10 times each for \(n =\) 5, 10, 20, 40, 80, and 160, then records and averages the results and makes a log-log plot of the average \(r\) vs. \(n\text{.}\) Once your program is running correctly, increase the maximum \(n\) (by factors of \(2\)) until the program stops running within 5 minutes.
🔗

🔗

Turn in the plot and the two programs. (Do not print any large random matrices.)

🔗

Prev Top Next