Matrix computations &
Numerical linear algebra

David Gleich

Purdue University

Fall 2012

Course number CS-51500

Tuesday and Thursday, 10:30-11:45am

Location Lawson 1106

Inverses

$\newcommand{\mat}[1]{\boldsymbol{#1}} \renewcommand{\vec}[1]{\boldsymbol{\mathrm{#1}}} \newcommand{\vecalt}[1]{\boldsymbol{#1}} \newcommand{\conj}[1]{\overline{#1}} \newcommand{\normof}[1]{\|#1\|} \newcommand{\onormof}[2]{\|#1\|_{#2}} \newcommand{\itr}[2]{#1^{(#2)}} \newcommand{\itn}[1]{^{(#1)}} \newcommand{\eps}{\varepsilon} \newcommand{\kron}{\otimes} \DeclareMathOperator{\diag}{diag} \DeclareMathOperator{\trace}{trace} \DeclareMathOperator{\tvec}{vec} \newcommand{\prob}{\mathbb{P}} \newcommand{\probof}[1]{\prob\left\{ #1 \right\}} \newcommand{\pmat}[1]{\begin{pmatrix} #1 \end{pmatrix}} \newcommand{\bmat}[1]{\begin{bmatrix} #1 \end{bmatrix}} \newcommand{\spmat}[1]{\left(\begin{smallmatrix} #1 \end{smallmatrix}\right)} \newcommand{\sbmat}[1]{\left[\begin{smallmatrix} #1 \end{smallmatrix}\right]} \newcommand{\RR}{\mathbb{R}} \newcommand{\CC}{\mathbb{C}} \newcommand{\eye}{\mat{I}} \newcommand{\mA}{\mat{A}} \newcommand{\mB}{\mat{B}} \newcommand{\mC}{\mat{C}} \newcommand{\mD}{\mat{D}} \newcommand{\mE}{\mat{E}} \newcommand{\mF}{\mat{F}} \newcommand{\mG}{\mat{G}} \newcommand{\mH}{\mat{H}} \newcommand{\mI}{\mat{I}} \newcommand{\mJ}{\mat{J}} \newcommand{\mK}{\mat{K}} \newcommand{\mL}{\mat{L}} \newcommand{\mM}{\mat{M}} \newcommand{\mN}{\mat{N}} \newcommand{\mO}{\mat{O}} \newcommand{\mP}{\mat{P}} \newcommand{\mQ}{\mat{Q}} \newcommand{\mR}{\mat{R}} \newcommand{\mS}{\mat{S}} \newcommand{\mT}{\mat{T}} \newcommand{\mU}{\mat{U}} \newcommand{\mV}{\mat{V}} \newcommand{\mW}{\mat{W}} \newcommand{\mX}{\mat{X}} \newcommand{\mY}{\mat{Y}} \newcommand{\mZ}{\mat{Z}} \newcommand{\mLambda}{\mat{\Lambda}} \newcommand{\mPbar}{\bar{\mP}} \newcommand{\ones}{\vec{e}} \newcommand{\va}{\vec{a}} \newcommand{\vb}{\vec{b}} \newcommand{\vc}{\vec{c}} \newcommand{\vd}{\vec{d}} \newcommand{\ve}{\vec{e}} \newcommand{\vf}{\vec{f}} \newcommand{\vg}{\vec{g}} \newcommand{\vh}{\vec{h}} \newcommand{\vi}{\vec{i}} \newcommand{\vj}{\vec{j}} \newcommand{\vk}{\vec{k}} \newcommand{\vl}{\vec{l}} \newcommand{\vm}{\vec{l}} \newcommand{\vn}{\vec{n}} \newcommand{\vo}{\vec{o}} \newcommand{\vp}{\vec{p}} \newcommand{\vq}{\vec{q}} \newcommand{\vr}{\vec{r}} \newcommand{\vs}{\vec{s}} \newcommand{\vt}{\vec{t}} \newcommand{\vu}{\vec{u}} \newcommand{\vv}{\vec{v}} \newcommand{\vw}{\vec{w}} \newcommand{\vx}{\vec{x}} \newcommand{\vy}{\vec{y}} \newcommand{\vz}{\vec{z}} \newcommand{\vpi}{\vecalt{\pi}}$

In this lecture, we’ll look into the inverse of a matrix, and find out which matrices are invertible. These notes roughly follow Trefethen and Bau, section 1.

Background

Let $\mA \in \RR^{m \times n} = \bmat{ \va_1 & \cdots & \va_n}$. Recall that

$$\text{range}(\mA) = \text{span}(\va_1, \ldots, \va_n),$$ $$\text{rank}(\mA) = \text{dim}(\text{range}(\mA)).$$

We call $\mA \in \RR^{m \times n}$ full rank if $\text{rank}(\mA) = \min(m, n)$.

Full rank matrices

Full rank matrices have the important property that they give rise to one-to-one maps between $\RR^{n}$ and $\RR^{m}$. Let’s show this.

Theorem (From Trefethen and Bau, Theorem 1.2) Let $m \ge n$, a matrix is full rank if and only if it maps no two distinct vectors to the same vector.

Proof If a matrix is full rank, then it has $n$ linearly independent column vectors. These vectors are a basis for $\text{range}(\mA)$. This, in turn, implies that any vector in $\text{range}(\mA)$ has a unique representation in this basis. (If not, then $\mA \vc_1 = \mA \vc_2$ and so $\mA$ has linearly dependent columns, which it can’t!) Thus, any vector $\mA \vy$ corresponds to a unique $\vy$.

We also have to prove the reverse direction, but this is easier to prove via the contrapositive. If $\mA$ is not full rank, then it’s columns are linearly dependent. Hence, there exists a vector $\vc$ such that $\mA \vc = 0$. Let $\vy$ be any vector in $\RR^{n}$, then $\mA \vy = \mA(\vy + \vc)$ and so we have two distinct vectors that give us the same result.

There’s a great picture I could put here, but it’s too tricky. The point is that we have a one-to-one map between $\RR^{n}$ and $\text{range}(\mA)$, which is a subset of $\RR^{m}$ when $m \ge n$. Because this map is one-to-one, it’s invertible! So we can take any vector $\vb \in \text{range}(\mA)$ and find

$$\mA \vx = \vb$$

for some $\vx \in \RR^{n}$.

Linear systems

It’s worth repeating this equation because it’s so fundamental to the rest of the class – and the entire field.

We call

$$\mA \vx = \vb$$

a linear system of equations.

Usually these are defined with squares matrices $\mA$.

Square, full rank matrices

Let $\mA \in \RR^{n \times n}$ be a full-rank matrix. What we’ve shown above is that any vector in $\RR^{n}$ can be written as $\mA \vx$ for some unique $\vx$.

Thus, we can find the following $n$ vectors:

$$\mA \vx_i = \ve_i \qquad i = 1, \ldots, n.$$

If we write this as a matrix equation, we have:

$$\mA \mX = \mI.$$

The matrix $\mX$ is called the inverse and usually written $\mA^{-1}$.

The matrix inverse

We’ve shown that $\mA \in \RR^{n \times n}$ and full rank has an inverse $\mA^{-1}$ such that

$$\mA \mA^{-1} = \mI.$$

Let’s study a few properties of this inverse.

First, does $\mA^{-1} \mA = \mI$ too? We’ll show this is the case. Let $\mA \mX = \mI$ and let $\mY \mA = \mI$. Then

$$\mY \mA \mX = (\mY \mA) \mX = \mX,$$

but also

$$\mY \mA \mX = \mY (mA \mX) = \mY.$$

Thus, $\mX = \mY$.

Second, $(\mA \mB)^{-1} = \mB^{-1} \mA^{-1}$ assuming that $\mA$ and $\mB$ are square. The standard way to check that you have the inverse of a particular matrix is just to show that it satifies $\mA \mX = \mI$. In this case:

$$(\mA \mB) (\mB^{-1} \mA^{-1}) = \mA (\mB \mB^{-1}) \mA^{-1} = (\mA \mA^{-1} = \mI.$$

where we’ve canceled all the inverse pairs represented by parentheses.

When is a matrix full rank?

The following set of statements from Trefthen and Bau helps to characterize when a matrix has an inverse. Let $\mA \in \RR^{n \times n}$, these statements are all equivalent to each other:

1. $\mA$ has an inverse $\mA^{-1}$
2. $\mA$ has rank $n$
3. $\text{range}(\mA) = \RR^{n}$.
4. (not fully covered) $\text{null}(\mA) = \{ 0 \}$ (null is the nullspace).
5. (not fully covered) 0 is not an eigenvalue of $\mA$
6. (not fully covered) 0 is not a singular value of $\mA$
7. (not fully covered) $\text{det}(\mA) \not= 0$

Solving a linear system

Let $\mA \in \RR^{n \times n}$ be full-rank. Then the linear system:

$$\mA \vx = \vb$$

has solution

$$\vx = \mA^{-1} \vb.$$

Be warned, this is not a good way to find $\vx$ unless $\mA$ is very special. In this class, we will see many superior procedures to find $\vx$ that satifies this linear system. A good way to demonstrate that you have not learned the material is to utilize this idea in your programs.