Matrix Computations

David Gleich

Purdue University

Fall 2024

Course number CS-51500

Tuesday-Thursday 10:30-11:45pm.

Basic Notation

Let us begin by introducing basic notation for matrices and vectors.

Matrices

We'll use $\RR$ to denote the set of real-numbers and $\CC$ to denote the set of complex numbers.

We write the space of all $m \times n$ real-valued matrices as $\RR^{m \times n}$. Each $$\mA \in \RR^{m \times n} \text{ is } \bmat{ A_{1,1} & \cdots & A_{1,n} \\ \vdots & & \vdots \\ A_{m,1} & \cdots & A_{m,n} } \text{ where } A_{i,j} \in \RR.$$ Sometimes, I'll write: $$\bmat{ a_{1,1} & \cdots & a_{1,n} \\ \vdots & & \vdots \\ a_{m,1} & \cdots & a_{m,n} }$$ instead. With only a few exceptions, matrices are written as bold, capital letters. Sometimes, we'll use a capital greek letter. Matrix elements are written as sub-scripted, unbold letters.
When clear from context, $$A_{i,j} \text{ is written } A_{ij}$$ instead, e.g. $A_{11}$ instead of $A_{1,1}$.

In class I'll usually write matrices with just upper-case letters. If you are unsure if something is a matrix or an element, raise your hand and ask, or quietly ask a neighbor.

Another notation for $\mA \in \RR^{m \times n}$ is $$\mA : n \times n.$$
Sometimes this is nicer to write on the board.

Vectors

We write the set of length-$n$ real-valued vectors as $\RR^{n}$. Each $$\vx \in \RR^{n} \text{ is } \bmat{ x_{1} \\ \vdots \\ x_{n} } \text{ where } x_i \in \RR.$$ Vectors are denoted by lowercase, bold letters. As with matrices, elements are sub-scripted, unbold letters. Sometimes, we'll write vector elements as $$x_i \text{ or } [x]_i \text{ or } x(i).$$ Usually, this choice is motivated by a particular application. Throughout the class, vectors are column vectors.

In class I'll usually write vectors with just lower-case letters and will try to follow the convention of underlining them.

Scalars

Lower-case greek letters are scalars.

Quick test

Identify the following:

$$\vf, z_1, \vx_1, \alpha, \beta, \mC, \mC_1, \mat{\Sigma}, B_{i,j}, \vb_{i,j}$$

Operations

Transpose Let $\mA : m \times n$, then $$\mB : n \times m = \mA^T \text { has } B_{i,j} = A_{j,i}.$$

Example $\mA = \sbmat{ 2 & 3 \\ 1 & 4 \\ 3 & -1 } \quad \mA^T = \sbmat{ 2 & 1 & 3 \\ 3 & 4 & -1 }$

Hermitian (Also called conjugate transpose) Let $\mA \in \CC^{m \times n}$, then $$\mB \in \CC^{n \times m} = \mA^* = \mA^{H} \text { has } B_{i,j} = \conj{A}_{j,i}.$$

Example $\mA = \sbmat{ 2 & 3 \\ i & 4 \\ & 3 & -i } \quad \mA^* = \sbmat{ 2 & -i & 3 \\ 3 & 4 & i }$

Addition Let $\mA : m \times n$ and $\mB : m \times n$, then $$\mC : m \times n = \mA + \mB \implies C_{i,j} = A_{i,j} + B_{i,j}.$$

Example $\mA = \sbmat{ 2 & 3 \\ 1 & 4 \\ 3 & -1 }, \mB = \sbmat{ 1 & -1 \\ 2 & 3 \\ -1 & 1 }$ $\mA + \mB = \sbmat{3 & -2 \\ 3 & 2 \\ 2 & 0 }$.

Scalar Multiplication Let $\mA : m \times n$ and $\alpha \in \RR$, then $$\mC : m \times n = \alpha \mA + \mB \implies C_{i,j} = \alpha A_{i,j}.$$

Example $\mA = \sbmat{ 2 & 3 \\ 1 & 4 \\ 3 & -1 }, 5 \mA = \sbmat{ 10 & 15 \\ 5 & 20 \\ 15 & -5 }$

Matrix Multiplication Let $\mA : m \times n$ and $\mB : n \times k$, then $$\mC : m \times k = \mA \mB \implies C_{i,j} = \sum_{r=1}^{n} A_{i,r} B_{r,j}.$$

Matrix-vector Multiplication Let $\mA : m \times n$ and $\vx \in \RR^{n}$, then $$\vc \in \RR^{m} = \mA \vx \implies c_i = \sum_{j=1}^n A_{i,j} x_j.$$ This operation is just a special case of matrix multiplication that follows from treating $\vx$ and $\vc$ as $n \times 1$ and $m \times 1$ matrices, respectively.

Vector addition, Scalar vector multiplication These are just special cases of matrix addition and scalar matrix multiplication where vectors are viewed as $n \times 1$ matrices.

Partitioning

It is often useful to represent a matrix as a collection of vectors. In this case, we write $$\mA : m \times n = \bmat{ \va_1 & \va_2 & \cdots & \va_n }$$ where each $\va_j \in \RR^{m}$. This form corresponds to a partition into columns.

Alternatively, we may wish to partition a matrix into rows. $$\mA : m \times n = \bmat{ \vr_1^T \\ \vr_2^T \\ \vdots \\ \vr_m^T }.$$ Here, each $\vr_i \in \RR^{n}$.

Using the column partitioning: $$\mA \vx = \bmat{ \va_1 & \va_2 & \cdots & \va_n } \bmat{ x_1 \\ x_2 \\ \vdots \\ x_n } = \sum_j x_j \va_j.$$ And with the row partitioning: $$\mA \vx = \bmat{ \vr_1^T \\ \vr_2^T \\ \vdots \\ \vr_m^T } \vx = \bmat{ \vr_1^T \vx \\ \vr_2^T \vx \\ \vdots \\ \vr_m^T \vx }.$$

Another useful partitioned representation of a matrix is into blocks: $$\mA = \bmat{\mA_{1,1} & \mA_{1,2} \\ \mA_{2,1} & \mA_{2,2} }$$ or
$$\mA = \bmat{\mA_{1,1} & \mA_{1,2} & \mA_{1,3} \\ \mA_{2,1} & \mA_{2,2} & \mA_{2,3} \\ \mA_{3,1} & \mA_{3,2} & \mA_{3,3} }.$$ Here, the sizes "just have to work out" in the vernacular. Formally, all $\mA_{i,\cdot}$ must have the same number of rows and all $\mA_{\cdot,j}$ must have the same number of columns.