Working through problem 5, Section 1.7

One of the problems assigned for the homework due Sep 17 is Exercise from 6 section 1.7. This is me working out its close analogue, problem 5. It asks you to determine whether the columns of the matrix

$$ A= \begin{bmatrix} \phantom{-}0 & -8 & \phantom{-}5 \\ \phantom{-}3 & -7 & \phantom{-}4 \\ -1 & \phantom{-}5 & -4 \\ \phantom{-}1 & -3 & \phantom{-}2 \end{bmatrix} $$

are linearly independent. We'll do this a couple of ways, each time letting Python finish the work for us.

Via linear systems

First, recall the following characterization of linear independence from the section Linear Independence of Matrix Columns in section 1.7 of your textbook:

The columns of a matrix $A$ are linearly independent if and only if the matrix equation $A{\bf x}={\bf 0}$ has only the trivial solution ${\bf x}={\bf 0}$.

This means that it is enough to solve that matrix equation, which in turn we know from the lectures and earlier textbook sections corresponds to the linear system with extended matrix

$$ E= \begin{bmatrix} A&{\bf 0} \end{bmatrix} $$

obtained by appending the all-zero column to $A$. We know by now how to solve systems with Python:

In [1]:
from sympy import *
from sympy.solvers.solveset import linsolve
In [2]:
x1, x2, x3 = symbols('x1, x2, x3')
In [3]:
E=Matrix([[0,-8,5,0],[3,-7,4,0],[-1,5,-4,0],[1,-3,2,0]])
In [4]:
linsolve(E, (x1, x2, x3))
Out[4]:
$\displaystyle \left\{\left( 0, \ 0, \ 0\right)\right\}$

As you can see, the all-zero vector is indeed the unique solution to our system, so the answer is: yes, the columns of the matrix $A$ are linearly independent. There are other ways to attack this though.

Via column spaces

Column spaces are not introduced until later in the book, in Chapter 4, but you know enough from your reading Chapter 1 to define them here. First, recall (from section 1.3):

The span of a family of vectors ${\bf v}_1,\cdots, {\bf v}_n$ is the set of all linear combinations

$$ c_1 {\bf v}_1 + \cdots + c_n {\bf v}_n $$

Now it's easy:

The column space of a matrix is the span of its columns.

And finally, we can use a result we will get around to later:

A collection of vectors ${\bf v}_i$, $1\le i\le n$ is linearly independent if and only if the span of the ${\bf v}_i$ is not the span of fewer than $n$ vectors.

And as a conclusion,

The columns of an $m\times n$ matrix are linearly independent if and only if its column space cannot be spanned by strictly fewer than $n$ vectors.

Now, SymPy has a built-in facility for "computing" column spaces, i.e. giving you back a set of vectors of as small a size as possible that spans the column space of a matrix. So the recipe for determining (through SymPy) whether an $m\times n$ matrix has linearly independent columns is simple:

  1. call this SymPy function on the matrix (I'll do this below), and
  2. see whether it returns a list of strictly fewer than $n$ vectors

Let's implement this.

In [5]:
A=Matrix([[0,-8,5],[3,-7,4],[-1,5,-4],[1,-3,2]])
In [6]:
A.columnspace()
Out[6]:
[Matrix([
 [ 0],
 [ 3],
 [-1],
 [ 1]]),
 Matrix([
 [-8],
 [-7],
 [ 5],
 [-3]]),
 Matrix([
 [ 5],
 [ 4],
 [-4],
 [ 2]])]

That doesn't look that good, does it? Easily mended:

In [7]:
init_printing(use_latex='mathjax')
In [8]:
A.columnspace()
Out[8]:
$\displaystyle \left[ \left[\begin{matrix}0\\3\\-1\\1\end{matrix}\right], \ \left[\begin{matrix}-8\\-7\\5\\-3\end{matrix}\right], \ \left[\begin{matrix}5\\4\\-4\\2\end{matrix}\right]\right]$

Anyway, the point is that the matrix had 3 columns to begin with, and SymPy says its column space cannot be spanned by fewer vectors. In conclusion, the columns must be linearly independent. This agrees with the answer we got through the other method.