Matrix Computations

David Gleich

Purdue University

Fall 2023

Course number CS-51500

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

Common matrix structures

There are many common types of matrix and vector structure.

Specific matrices and vectors

The $n \times n$ identity matrix is written: $$\mI = \bmat{1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & \vdots \\ \vdots & \cdots & \ddots & 0 \\ 0 & \cdots & 0 & 1}$$ This matrix is rarely written with it's explicit dimension as that can almost always be inferred by context. That is to say, the dimension of the identity matrix is whatever it needs to be such that the matrix equation makes sense. For clarity, we might sometimes write: $$\mI_n$$ to denote the $n \times n$ matrix explicitly. Thus, $$\mI_3 = \bmat{1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1}.$$

The identity matrix has the property that $\mA \mI = \mA$ for any matrix $\mA$. It's like multiplying by 1.

We denote the $i$th column of the identity matrix by $\ve_i$: $$\ve_i = \bmat{0 \\ \vdots \\ 1 \rlap{\text{ <script type="math/tex">i$$ th position }} \\ 0 \\ \vdots \\ 0}. For instance, $$\ve_2 = \bmat{ 0 & 1 & 0 }^T.$$

Using these vectors, we can write the $i$th column of any matrix as $$\mA \ve_i.$$

It is, perhaps, alarming that $\ve_i$ is frequently used without specifying its dimension. However, just like the identity matrix above, it is almost always possible to work out the dimension. If we believe it is helpful to specify it, we'll use $\ve_i\itn{n}$.

Finally, the vector $\ve$ will be used to denote the vector of all ones: $$\ve = \bmat{1 \\ 1 \\ \vdots \\ 1}.$$ Except sometimes it will be used as an error vector for a problem.

Some people use the matrix $\mJ$ to represent the matrix of all ones: $$\mJ = \bmat{ \ve & \ve & \cdots & \ve }.$$ I don't think we'll need that in this class, however.

Elemental structures

Throughout these examples, the matrix is $\mA$, and it's elements are $A_{i,j}$.

Diagonal We call a matrix diagonal if all of the non-zero entries are those $A_{i,j}$ where $i=j$, that is, on the "diagonal" of the matrix.

Examples $\mA = \bmat{1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & -1}.$ The identity matrix is another diagonal matrix.

Operationally We use the operator $\diag$ to extract the diagonal from a matrix. For instance, $\ve = \diag(\mI)$. This can also be used to "create" a matrix: $\mD = \diag(\vd)$ has $D_{i,i} = d_i$. So the diag operation gets a bit overloaded.

Triangular We call a matrix upper triangular if all of the non-zero entries are those $A_{i,j}$ where $j \ge i$. That is, if it looks like an upper triangle. A matrix is lower triangular if all of the non-zero entries are those $A_{i,j}$ where $i \ge j$. A matrix is triangular if it's either upper or lower triangular.

Examples $\mA = \bmat{1 & 2 & 3 \\ 0 & -2 & -3 \\ 0 & 0 & 1}$ is upper triangular. $\mA = \bmat{1 & 0 & 0 \\ -1 & 2 & 0 \\ 1 & 0 & 1}$ is lower triangular.

Operationally The operators triu and tril are sometimes used to denote the upper and lower triangular part of a matrix. They are implemented in Matlab, which is useful!

Symmetric We call a matrix symmetric if $A_{i,j} = A_{j,i}$ or equivalently, $\mA = \mA^T$.

Examples $\mA = \bmat{1 & 2 \\ 2 & 1}$.

Notes

• The generalization of symmetric to complex-valued matrices is called Hermitian. A matrix is Hermitian if $\mA = \mA^*$ for the complex adjoint or Hermitian operator, that is, $A_{i,j} = \conj{A_{j,i}}$ for the complex conjugate "bar".

• Any real-valued matrix $\mA$ can be written as: $\mA = \mS + \mK$ where $\mS$ is symmetric and $\mK$ is skew-symmetric. A matrix is skew-symmetric if $\mK = -\mK^T$. In this case, $\mS = (\mA + \mA^T)/2$ and $\mK = (\mA - \mA^T)/2$. If $\mA$ is symmetric, then $\mS = \mA$ and $\mK = 0$.

Orthogonal A matrix is orthogonal if $\mA^T \mA = \mI$. We'll get into why orthogonal matrices are special soon.

Examples The identity matrix $\mI$ is orthogonal. We'll see more about orthogonal matrices soon -- it's a very special structure!

Permutation A permutation matrix "shuffles" elements of a vector. Each column of a permutation matrix is a vector $\ve_i$ and a permutation matrix must also be orthogonal.

Examples $\mA = \bmat{0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0}$. This matrix expresses the permutation $2 \to 1, 3 \to 2, 1 \to 3$. We can see this by: $\mA \bmat{0.5 \\ -0.5 \\ 1} = \bmat{-0.5 \\ 1 \\ 0.5}$.

Sparse matrices

Sparse matrices are those where the vast majority of the elements in the matrix are zero. For instance: $$\mA = \bmat{0 & 2 & 0 \\ 0 & 0 & 0 \\ 1 & 0 & 0}.$$ Of the $9$ entries in the matrix, there are only two non-zeros. Later in the class, we'll see how to take advantage of this structure.