Matrix Computations

David Gleich

Purdue University

Fall 2023

Course number CS-51500

Tuesday-Thursday 1:30-2:45pm. Hampton 2123

Common matrix structures

We now illuminate some of the relationships between matrix computations and linear algebra.

Why is this stuff important? The important bit is the concept of the rank of a matrix. This gives the dimension of the vector-space associated with the matrix. So it's worth reviewing up to the point of rank.

Sets of vectors

Linearly independent A set of vectors $\{ \vx_1, \ldots, \vx_k \}$ in $\RR^{n}$ is called linearly independent if $$\sum_{i=1}^{k} \alpha_i \vx_i = 0$$ imples $\alpha_i = 0$ all $i$.

Examples The vectors $\vx_1 = \bmat{1 \\ 2}$ and $\vx_2 = \bmat{2 \\ 3}$ are linearly independent. This can be verified by showing that the system of equations: $$\alpha_1 + 2 \alpha_2 = 0 \text{ and } 2 \alpha_1 + 3 \alpha_2 = 0$$ only has the solution $\alpha_1 = \alpha_2 = 0$. However, the vectors $\vx_1 = \bmat{1 \\ 2}$ and $\vx_2 = \bmat{2 \\ 4}$ are not linearly independent because $2\vx_1 - \vx_2 = 0$.

As a matrix The property of being linearly independent is easy to state as a matrix. Suppose that $\mX$ is an $n \times k$ matrix where $\vx_i$ is the $i$th column: $$\mX = \bmat{ \vx_1 & \cdots & \vx_k }.$$ Then the set of vectors is linearly independent if $\mX \va = 0$ implies that $\va = 0$.

Span (not spam) The span of a set of vectors is the set of all linear combinations. $$\text{span}(\vx_1, \ldots, \vx_k) = \{ \sum_{i=1}^{k} \alpha_i \vx_i, \alpha_i \in \RR \}.$$

Subspaces

Defining a vector spaces is best left to Wikipedia:

• Vector space

Suffice it to say that that the set $\RR^{n}$ is a vector-space with the field of real-numbers as scalars.

A subset $V \subset \RR^{n}$ is called a subspace if it also satisfies the properties of being a vector-space itself.

Example Let $V = \{ \alpha \vx, \alpha \in RR \}$ for some vector $\vx \in \RR^{n}$. Then $V$ is a subspace of $\RR^{n}$.

Spans and subspaces The example we just saw shows that $\text{span}(\vx)$, the span of a single vector, is a subspace. This is true in general: $\text{span}(\vx_1, \ldots, \vx_k)$ is a subspace.

Linearly independent spans Let $\vx_1, \ldots, \vx_k$ be linearly independent. Then for $\vb \in \text{span}(\vx_1, \ldots, \vx_k)$, there exists a unique set of $\alpha_i$'s such that $\vb = \sum_{i=1}^{k} \alpha_i \vx_k$. As a matrix, this is saying that the system of equations: $$\vb = \mX \va$$ has a unique solution $\va$ where $$\mX = \bmat{ \vx_1, \ldots, \vx_k }.$$

Subspaces to bases and dimensions For any subspace $V \subseteq \RR^{n}$, we can find always find a set $S$ of linearly independent vectors $S = \{ \vx_1, \ldots, \vx_k \}$ such that $V = \text{span}(\vx_1, \ldots, \vx_k)$. We call any such set a basis for the subspace $V$.

IMPORTANT Any basis for a subspace always has the same number of vectors. Thus, the number of vectors in a subspace is a unique property of a vector space and is the dimension of the vector-space.

This ends our discussion of subspaces. Now we'll see how we can use subspaces to discuss matrices

Matrices to subspaces

Given a matrix $\mA \in \RR^{m \times n} = \bmat{\va_1, \ldots, \va_n}$.

Range The range of a matrix is the subspace: $$\text{range}(\mA) = \{ \vy \in \RR^{m} : y = \mA \vx \text{ for all } \vx \in \RR^{n} \}.$$ Note that $$\text{range}(\mA) = \text{span}\{\va_1, \ldots, \va_n\}.$$ So the range is just one particular span of a set of vectors.

Rank

Perhaps the most important thing in these notes is the concept of rank. At this point, rank is simple.

$$\text{rank}(\mA) = \text{dim}(\text{range}(\mA))$$

That is, the rank of $\mA$ is the dimension of the subspace given by the range of $\mA$. This property is fundamentally important.

For instance, if $\mA \in \RR^{m \times n}$ with $m \ge n$ and $\text{rank}(\mA) = n$, then we know that $$\mA = \bmat{\va_1, \ldots, \va_n}$$ has a set of linearly independent column vectors!

Example Here's where we can use some of our matrix algebra to prove a statement. Let $\mP$ be an $n \times n$ permutation matrix. Show that $\text{rank}(\mA \mP) = \text{rank}(\mA)$.

Proof Sketch A permutation matrix just reorders the columns of the matrix. This won't change anything in the range of $\mA$. So the set of vectors in the range of $\mA$ won't change. Thus, the dimension of that vector space won't change.

Key question How do we compute rank?

Answer Use a matrix decomposition!

Useful matrix decompositions

Let $\mA \in \RR^{m \times n}$ be a matrix. The following are matrix decompositions exist for any matrix:

1. $\mA = \mQ \mR$ where $\mQ$ is $m \times m$ and orthogonal, and $\mR$ is $m \times n$ and upper-triangular.

2. $\mA = \mU \mat{\Sigma} \mV^T$ where $\mU$ is $m \times m$ and orthogonal, $\mV$ is $n \times n$ and orthogonal, and $\mat{\Sigma}$ is $m \times n$ and diagonal, with diagonal entries $\sigma_1 \ge \sigma_2 \ge \cdots \ge \sigma_n \ge 0$. (That is, sorted in decreasing order and non-negative.)

3. $\mA = \mP \mL \mU \mQ$ where $\mP$ and $\mQ$ are permutation matrices and $\mL$ and $\mU$ are lower and upper triangular.

These decompositions expose the rank of a matrix in various ways. For instance, the number of entries on the diagonal of $\mSigma$ that are non-zero is equal to the rank of the matrix.