# Vectors, matrices and norms

## Learning Objectives

• Understanding matrix-vector multiplications
• Special matrix types
• How we can “measure” vectors
• How we can “measure” matrices

## Vector Spaces

A vector space is a set $$V$$ of vectors and a field $$F$$ (elements of F are called scalars) with the following two operations:

1. Vector addition: $$\forall \mathbf{v},\mathbf{w} \in V$$, $$\mathbf{v} + \mathbf{w} \in V$$
2. Scalar multiplication: $$\forall \alpha \in F, \mathbf{v} \in V$$, $$\alpha \mathbf{v} \in V$$

which satisfiy the following conditions:

1. Associativity (vector): $$\forall \mathbf{u}, \mathbf{v}, \mathbf{w} \in V$$, $$(\mathbf{u} + \mathbf{v}) + \mathbf{w} = \mathbf{u} + (\mathbf{v}+\mathbf{w})$$
2. Zero vector: There exists a vector $$\mathbf{0} \in V$$ such that $$\forall \mathbf{u} \in V, \mathbf{0} + \mathbf{u} = \mathbf{u}$$
3. Additive inverse (negatives): For every $$\mathbf{u} \in V$$, there exists $$\mathbf{-u} \in V$$, such that $$\mathbf{u} + \mathbf{-u} = \mathbf{0}$$.
4. Associativity (scalar): $$\forall \alpha, \beta \in F, \mathbf{u} \in V$$, $$(\alpha \beta) \mathbf{u} = \alpha (\beta \mathbf{u})$$
5. Distributivity: $$\forall \alpha, \beta \in F, \mathbf{u} \in V$$, $$(\alpha + \beta) \mathbf{u} = \alpha \mathbf{u} + \beta \mathbf{u}$$
6. Unitarity: $$\forall \mathbf{u} \in V$$, $$1 \mathbf{u} = \mathbf{u}$$

If there exist a set of vectors $$\mathbf{v}_1,\mathbf{v}_2\dots, \mathbf{v}_n$$ such that any vector $$\mathbf{x}\in V$$ can be written as a linear combination

with uniquely determined scalars $$c_1,\dots,c_n$$, the set $${\mathbf{v}_1,\dots, \mathbf{v}_n}$$ is called a basis for $$V$$. The size of the basis $$n$$ is called the dimension of $$V$$.

The standard example of a vector space is $$V=\mathbb{R}^n$$ with $$F=\mathbb{R}$$. Vectors in $$\mathbb{R}^n$$ are written as an array of numbers:

The dimension of $$\mathbb{R}^n$$ is $$n$$. The standard basis vectors of $$\mathbb{R}^n$$ are written as

A set of vectors $$\mathbf{v}_1,\dots,\mathbf{v}_k$$ is called linearly independent if the equation $$\alpha_1\mathbf{v}_1 + \alpha_2\mathbf{v}_2 + \dots + \alpha_k\mathbf{v}_k = \mathbf{0}$$ in the unknowns $$\alpha_1,\dots,\alpha_k$$, has only the trivial solution $$\alpha_1=\alpha_2 = \dots = \alpha_k = 0$$. Otherwise the vectors are linearly dependent, and at least one of the vectors can be written as a linear combination of the other vectors in the set. A basis is always linearly independent.

## Inner Product

Let $$V$$ be a real vector space. Then, an inner product is a function $$\langle\cdot, \cdot \rangle: V \times V \rightarrow \mathbb{R}$$ (i.e., it takes two vectors and returns a real number) which satisfies the following four properties, where $$\mathbf{u}, \mathbf{v}, \mathbf{w} \in V$$ and $$\alpha, \beta \in \mathbb{R}$$:

1. Positivity: $$\langle \mathbf{u}, \mathbf{u} \rangle \geq 0$$
2. Definiteness: $$\langle \mathbf{u}, \mathbf{u} \rangle = 0$$ if and only if $$\mathbf{u} = 0$$
3. Symmetric: $$\langle \mathbf{u}, \mathbf{v} \rangle = \langle \mathbf{v}, \mathbf{u} \rangle$$
4. Linearity: $$\langle \alpha \mathbf{u} + \beta \mathbf{v}, \mathbf{w} \rangle = \alpha \langle \mathbf{u}, w \rangle + \beta \langle \mathbf{v}, \mathbf{w} \rangle$$

The inner product intuitively represents the similarity between two vectors. Two vectors $$\mathbf{u}, \mathbf{v} \in V$$ are said to be orthogonal if $$\langle \mathbf{u}, \mathbf{v} \rangle = 0$$.

The standard inner product on $$\mathbb{R}^n$$ is the dot product :$\langle \mathbf{x}, \mathbf{y}\rangle = \mathbf{x}^T\mathbf{y} = \sum_{i=1}^nx_i y_i.$

## Linear Transformations and Matrices

A function $$f: V \to W$$ between two vector spaces $$V$$ and $$W$$ is called linear if

1. $$f(\mathbf{u} + \mathbf{v}) = f(\mathbf{u}) + f(\mathbf{v})$$, for any $$\mathbf{u},\mathbf{v} \in V$$
2. $$f(c\mathbf{v}) = cf(\mathbf{v})$$, for all $$\mathbf{v} \in V$$ and all scalars $$c$$

$$f$$ is commonly called a linear transformation.

If $$n$$ and $$m$$ are the dimension of $$V$$ and $$W$$, respectively, then $$f$$ can be represented as an $$m\times n$$ rectangular array or matrix

The numbers in the matrix $$\mathbf{A}$$ are determined by the basis vectors for the spaces $$V$$ and $$W$$. To see how, we first review matrix vector multiplication.

### Matrix-vector multiplication

Let $$\mathbf{A}$$ be an $$m\times n$$ matrix of real numbers. We can also write $$\mathbf{A}\in\mathbb{R}^{m\times n}$$ as shorthand. If $$\mathbf{x}$$ is a vector in $$\mathbb{R}^n$$ then the matrix-vector product $$\mathbf{A}\mathbf{x} = \mathbf{b}$$ is a vector in $$\mathbf{R}^m$$ defined by:

We can interpret matrix-vector multiplications in two ways. Throughout this online textbook reference, we will use the notation ${\bf a}_i$ to refer to the $i^{th}$ column of the matrix ${\bf A}$ and ${\bf a}^T_i$ to refer to the $i^{th}$ row of the matrix ${\bf A}$.

1) Writing a matrix-vector multiplication as inner products of the rows ${\bf A}$:

2) Writing a matrix-vector multiplication as linear combination of the columns of ${\bf A}$:

$\mathbf{A}\mathbf{x} = x_1\mathbf{a}_{1} + x_2\mathbf{a}_{2} + \dots x_n\mathbf{a}_{n} = x_1\begin{bmatrix}a_{11} \\ a_{21} \\ \vdots \\ a_{m1}\end{bmatrix} + x_2\begin{bmatrix}a_{12} \\ a_{22} \\ \vdots \\ a_{m2}\end{bmatrix} + \dots + x_n\begin{bmatrix}a_{1n} \\ a_{2n} \\ \vdots \\ a_{mn}\end{bmatrix}$

It is this representation that allows us to express any linear transformation between finite-dimensional vector spaces with matrices.

### Matrix Representation of Linear Transformations

Let $\mathbf{e}_1,\mathbf{e}_2,\dots,\mathbf{e}_n$ be the standard basis of $\mathbb{R}^n$. If we define the vector $\mathbf{z}_j = \mathbf{A}\mathbf{e}_j$, then using the interpretation of matrix-vector products as linear combinations of the column of $\mathbf{A}$, we have that:

where we have written the standard basis of $\mathbb{R}^m$ as $\hat{\mathbf{e}}_1,\hat{\mathbf{e}}_2,\dots,\hat{\mathbf{e}}_m$.

In other words, if $\mathbf{z}_j = \mathbf{A}\mathbf{e}_j$ is written as a linear combination of the basis vectors of $\mathbb{R}^m$, the element $a_{ij}$ is the coefficient corresponding to $\hat{\mathbf{e}}_{i}$.

#### Example

Let’s try an example. Suppose that $$V$$ is a vector space with basis $$\mathbf{v}_1,\mathbf{v}_2,\mathbf{v}_3$$, and $$W$$ is a vector space with basis $$\mathbf{w}_1,\mathbf{w}_2$$. Then $$V$$ and $$W$$ have dimension 3 and 2, respectively. Thus any linear transformation $$f: V \to W$$ can be represented by a $$2\times 3$$ matrix. We can introduce column vector notation, so that vectors $$\mathbf{v} = \alpha_1\mathbf{v}_1 + \alpha_2\mathbf{v}_2 + \alpha_3\mathbf{v}_3$$ and $$\mathbf{w} = \beta_1\mathbf{w}_1 + \beta_2\mathbf{w}_2$$ can be written as

We have not specified what the vector spaces $$V$$ and $$W$$, but it is fine if we treat them like elements of $$\mathbb{R}^3$$ and $$\mathbb{R}^2$$.

Suppose that the following facts are known about the linear transformation $$f$$:

• $$f(\mathbf{v}_1) = \mathbf{w}_1$$
• $$f(\mathbf{v}_2) = 5\mathbf{w}_1 - \mathbf{w}_2$$
• $$f(\mathbf{v}_3) = 2\mathbf{w}_1 + 2\mathbf{w}_2$$

This is enough information to completely determine the matrix representation of $$f$$. The first equation tells us

So we know $a_{11} = 1,\ a_{21} = 0$. The second equation tells us that

So we know $a_{12} = 5,\ a_{22} = -1$. Finally, the third equation tells us

Thus, $$a_{13} = 2,\ a_{23} = 2$$, and the linear transformation $$f$$ can be represented by the matrix:

It is important to note that the matrix representation not only depends on $$f$$, but also our choice of basis. If we chose different bases for the vector spaces $$V\text{ and } W$$, the matrix representation of $$f$$ would change as well.

## Special Matrices

### Zero Matrices

The $$m \times n$$ zero matrix is denoted by $${\bf 0}_{mn}$$ and has all entries equal to zero. For example, the $$3 \times 4$$ zero matrix is

### Identity Matrices

The $$n \times n$$ identity matrix is denoted by $${\bf I}_n$$ and has all entries equal to zero except for the diagonal, which is all 1. For example, the $$4 \times 4$$ identity matrix is

### Diagonal Matrices

A $$n \times n$$ diagonal matrix has all entries equal to zero except for the diagonal entries. We typically use $${\bf D}$$ for diagonal matrices. For ecample, $$4 \times 4$$ diagonal matrices have the form:

### Triangular Matrices

A lower-triangular matrix is a square matrix that is entirely zero above the diagonal. We typically use $${\bf L}$$ for lower-triangular matrices. For example, $$4 \times 4$$ lower-triangular matrices have the form:

An upper triangular matrix is a square matrix that is entirely zero below the diagonal. We typically use $${\bf U}$$ for upper-triangular matrices. For example, $$4 \times 4$$ upper-triangular matrices have the form:

Properties of triangular matrices:

1. An $$n \times n$$ triangular matrix has $$n(n-1)/2$$ entries that must be zero, and $$n(n+1)/2$$ entries that are allowed to be non-zero.
2. Zero matrices, identity matrices, and diagonal matrices are all both lower triangular and upper triangular.

### Permutation Matrices

A permuation matrix is a square matrix that is all zero, except for a single entry in each row and each column which is 1. We typically use $${\bf P}$$ for permutation matrices. An example of a $$4 \times 4$$ permutation matrix is

The properties of a permutation matrix are:

1. Exactly $$n$$ entries are non-zero.
2. Multiplying a vector with a permutation matrix permutes (rearranges) the order of the entries in the vector. For example, using $${\bf P}$$ above and $$x = [1, 2, 3, 4]^T$$, the product is $${\bf Px} = [2, 4, 1, 3]^T$$.
3. If $$P_{ij} = 1$$ then $$({\bf Px})_i = x_j$$.
4. The inverse of a permutation matrix is its transpose, so $${\bf PP}^T = {\bf P}^T{\bf P} = {\bf I}$$.

### Matrices in Block Form

A matrix in block form is a matrix partitioned into blocks. A block is simply a submatrix. For example, consider

where $${\bf A}$$, $${\bf B}$$, $${\bf C}$$, and $${\bf D}$$ are submatrices.

There are special matrices in block form as well. For instance, a block diagonal matrix is a block matrix whose off-diagonal blocks are zero matrices.

## Matrix Rank

The rank of a matrix is the number of linearly independent columns of the matrix. It can also be shown that the matrix has the same number of linearly indendent rows, as well. If $$\mathbf{A} \text{ is an } m \times n$$ matrix, then

1. $$\text{rank}(\mathbf{A}) \leq \text{min}(m,n)$$.
2. If $$\text{rank}(\mathbf{A}) = \text{min}(m,n)$$, then $$\mathbf{A}$$ is full rank. Otherwise, $$\mathbf{A}$$ is rank deficient.

A square $$n\times n$$ matrix $$\mathbf{A}$$ is invertible if there exists a square matrix $$\mathbf{B}$$ such that $$\mathbf{AB} = \mathbf{BA} = \mathbf{I}$$, where $$\mathbf{I}$$ is the $$n\times n$$ identity matrix. The matrix $$\mathbf{B}$$ is denoted by $$\mathbf{A}^{-1}$$. A square matrix is invertible if and only if it has full rank. A square matrix that is not invertible is called a singular matrix.

## Vector Norm

A vector norm is a function $\| \mathbf{u} \|: V \rightarrow \mathbb{R}^+_0$ (i.e., it takes a vector and returns a nonnegative real number) that satisfies the following properties, where $\mathbf{u}, \mathbf{v} \in V$ and $\alpha \in \mathbb{R}$:

1. Positivity: $\| \mathbf{u}\| \geq 0$
2. Definiteness: $\|\mathbf{u}\| = 0$ if and only if $\mathbf{u} = \mathbf{0}$
3. Homogeneity: $\|\alpha \mathbf{u}\| = \vert\alpha\vert \|\mathbf{u}\|$
4. Triangle inequality: $\|\mathbf{u} + \mathbf{v}\| \leq \|\mathbf{u}\| + \|\mathbf{v}\|$

A norm is a generalization of “absolute value” and measures the “magnitude” of the input vector.

#### The p-norm

The p-norm is defined as

$\|\mathbf{w}\|_p = (\sum_{i=1}^N \vert w_i \vert^p)^{\frac{1}{p}}$.

The definition is a valid norm when $p \geq 1$. If $0 \leq p \lt 1$ then it is not a valid norm because it violates the triangle inequality.

When $p=2$ (2-norm), this is called the Euclidean norm and it corresponds to the length of the vector.

#### Vector Norm Examples

Consider the case of $\mathbf{w} = [-3, 5, 0, 1]$, in this part we will show how to calculate the 1, 2, and $\infty$ norm of $\mathbf{w}$.

For the 1-norm:

For the 2-norm:

For the $\infty$-norm:

## Matrix Norm

A general matrix norm is a real valued function $\| {\bf A} \|$ that satisfies the following properties:

1. Positivity: $\|{\bf A}\| \geq 0$
2. Definiteness: $\|{\bf A}\| = 0$ if and only if ${\bf A} = 0$
3. Homogeneity: $\|\lambda {\bf A}\| = \vert\lambda\vert \|{\bf A}\|$ for all scalars $\lambda$
4. Triangle inequality: $\|{\bf A} + {\bf B}\| \leq \|{\bf A}\| + \|{\bf B}\|$

Induced (or operator) matrix norms are associated with a specific vector norm $\| \cdot \|$ and are defined as:

An induced matrix norm is a particular type of a general matrix norm. Induced matrix norms tell us the maximum amplification of the norm of any vector when multiplied by the matrix. Note that the definition above is equivalent to

In addition to the properties above of general matrix norms, induced matrix norms also satisfy the submultiplicative conditions:

#### Frobenius norm

The Frobenius norm is simply the sum of every element of the matrix squared, which is equivalent to applying the vector $2$-norm to the flattened matrix,

The Frobenius norm is an example of a general matrix norm that is not an induced norm.

#### The matrix p-norm

The matrix p-norm is induced by the p-norm of a vector. It is $\|{\bf A}\|_p := \max_{\|\mathbf{x}\|_p=1} \|{\bf A}\mathbf{x}\|_p$. There are three special cases:

For the 1-norm, this reduces to the maximum absolute column sum of the matrix, i.e.,

For the 2-norm, this reduces the maximum singular value of the matrix.

For the $\infty$-norm this reduces to the maximum absolute row sum of the matrix.

#### Matrix Norm Examples

Now we will go through a few examples with a matrix ${\bf C}$, defined below.

For the 1-norm:

For the 2-norm:

The singular values are the square roots of the eigenvalues of the matrix ${\bf C}^T {\bf C}$. You can also find the maximum singular values by calculating the Singular Value Decomposition of the matrix.

For the $\infty$-norm:

## ChangeLog

• 2020-04-27 Mariana Silva mfsilva@illinois.edu: updated notation and mat-vec section
• 2020-02-01 Peter Sentz: added more text from current slide deck