Text provided under a Creative Commons Attribution license, CC-BY. All code is made available under the FSF-approved MIT license. (c) Kyle T. Mandli

Note: This material largely follows the text “Numerical Linear Algebra” by Trefethen and Bau (SIAM, 1997) and is meant as a guide and supplement to the material presented there.

Numerical Linear Algebra¶

Numerical methods for linear algebra problems lies at the heart of many numerical approaches and is something we will spend some time on. Roughly we can break down problems that we would like to solve into three general problems, solving a system of equations

Projection problems or Linear Least Squares

and solving the eigenvalue problem

We examine each of these problems separately and will evaluate some of the fundamental properties and methods for solving these problems. We will be careful in deciding how to evaluate the results of our calculations and try to gain some understanding of when and how they fail.

Factorizations¶

For each fundamental problem, there are a range of algorithms to solve them, but all of these algorithms can often be succinctly described in terms of a matrix “factorization”, the ability to write an arbitrary matrix $A$ as a product of matrices with special properties (e.g. triangular, diagonal, orthogonal) that make solving the general problem straightforward. For example

To develop all of these algorithms in depth is a course in itself, however, here we will highlight some of the key factorizations and algorithms used in modern computational linear algebra. In particular we will highlight issues of accuracy, stability and computational cost particularly in the limit of large systems.

Some Example Problems¶

The number and power of the different tools made available from the study of linear algebra makes it an invaluable field of study. Before we dive in to numerical approximations we first consider some of the pivotal problems that numerical methods for linear algebra are used to address.

For this discussion we will be using the common notation $m \times n$ to denote the dimensions of a matrix $A$. The $m$ refers to the number of rows and $n$ the number of columns. If a matrix is square, i.e. $m = n$, then we will use the notation that $A$ is $m \times m$.

Systems of Equations¶

The first type of problem is to find the solution to a linear system of equations. If we have $m$ equations for $m$ unknowns it can be written in matrix/vector form,

For this example $A$ is an $m \times m$ matrix, denoted as being in $\mathbb{R}^{m\times m}$, and $\mathbf{x}$ and $\mathbf{b}$ are column vectors with $m$ entries, denoted as $\mathbb{R}^m$.

Example 1: Polynomial Fitting¶

In our previous work on interpolation we found that the unique interpolating polynomial of order $n$ through the $n+1$ points $(x_i, y_i)$ can be found by solving a Linear system of equations

where $V$ is a VanderMonde matrix whose columns are the basis functions $\phi_j(\mathbf{x})$ (e.g. the monomials) and $\mathbf{w}\in\mathbb{R}^{n+1}$ are the coefficients (weights) such that the interpolating polynomial is given uniquely by

Examples 2: Solution of Non-linear equations by Newton’s Method¶

Given a non-linear system of equations

Newton’s method provides an iterative method to find roots where at every step of the iteration a linear system of equations

Examples 3: Solution of Boundary Value problems by Finite Differences or Finite Elements¶

Given a general linear differential equation

where ${\cal L}$ is a linear differential operator e.g.

Finite difference or finite element discretizations usually reduce the continuous, infinite dimensional problem to a discrete linear problem of form

Where $\mathbf{u}$ and $\mathbf{f}$ are discrete approximations to the solution function and right hand side and $A$ is a discrete approximation to ${\cal L}$. Moreover, for many discretizations, $A$ can be very sparse.

Linear least squares¶

In a similar case as above, say we want to fit a particular function (could be a polynomial) to a given number of data points except in this case we have more data points than free parameters. In the case of polynomials this could be the same as saying we have $m$ data points but only want to fit a $n - 1$ order polynomial through the data where $n - 1 \leq m$. One of the common approaches to this problem is to minimize the “least-squares” error between the data and the resulting function:

E.g. Consider fitting the function

to data that has random noise added to it.

If our function $f(x)$ can be written as a linear combination of basis functions

then the linear system through $m$ points becomes $A\mathbf{w} = \mathbf{y}$ where $A$ is a generalized $m\times n$ vandermonde matrix

Which will be over-determined for $m > n$. However the Least-squares solution for the weights $\mathbf{w}$ will satisfy

we can guarantee that the error is minimized in the least-squares sense¹. (Although we will also show that this is not the most numerically stable way to solve this problem)

Define the data¶

Define basis functions and Vandermonde matrix¶

Eigenproblems¶

Eigenproblems come up in a variety of contexts and often are integral to many problem of scientific and engineering interest. It is such a powerful idea that it is not uncommon for us to take a problem and convert it into an eigenproblem.

One of my favorite examples The Tacoma Narrows Bridge Collapse

Or the original Google Page-Rank algorithm which essentially finds the dominant eigenvector of an enormous sparse Markov Matrix.

Here we introduce the idea and give some examples.

As a review, if $A \in \mathbb{C}^{m\times m}$ (a square matrix with complex values), a non-zero vector $\mathbf{v}\in\mathbb{C}^m$ is an eigenvector of $A$ with a corresponding eigenvalue $\lambda \in \mathbb{C}$ if

One way to interpret the eigenproblem is that we are attempting to ascertain the “action” of the matrix $A$ on some subspace of $\mathbb{C}^m$ where this action acts like scalar multiplication. This subspace is called an eigenspace.

General idea of EigenProblems¶

Rewriting the standard Eigen problem $A\mathbf{v}=\lambda\mathbf{v}$ for $A \in \mathbb{C}^{m\times m}$, $\mathbf{v}\in\mathbb{C}^m$ as

it becomes clear that for $\mathbf{v}$ to be non-trivial (i.e. $\neq \mathbf{0}$), requires that the matrix $(A-\lambda I)$ be singular,

This is equivalent to finding all values of $\lambda$ such that $|A-\lambda I| = 0$ (the determinant of singular matrices is always zero). However, it can also be shown that

which is a $m$th order polynomial in $\lambda$. Thus $P_m(\lambda)=0$ implies the eigenvalues are the $m$ roots of $P$, and the eigenspace corresponding to $\lambda_i$ is just $N(A-\lambda_i I)$

Solving EigenProblems¶

The temptation (and what we usually teach in introductory linear algebra classes) is to find the roots of $P_m(\lambda)$ to get the eigenvalues, then find the null-space of $A-\lambda I$.

However that would be wrong. The best algorithms for finding Eigenvalues are completely unrelated to rootfinding as we shall see (and in fact, the way you find the roots of polynomials is to find the eigenvalues of a “companion matrix”)

The Singular Value Decomposition¶

One of the most beautiful, and useful, factorizations is the Singular Value Decomposition (or SVD),

where $A$ is a general $m\times n$ matrix, $U$ and $V$ are unitary (orthogonal) matrices such that $U^TU=I^{m\times m}$, $V^TV = I^{n\times n}$ and $\Sigma$ is a diagonal matrix with real, positive diagonal entries (the singular values)

where $r$ is the rank of $A$

Applications of the SVD¶

The SVD combines all the aspects of basic linear algebra and is used in a large number of applications including

• diagnosing ill-conditioned matrices

• providing orthonormal bases for the 4-subspaces of $A$

• Solving linear systems and linear least-squares problems

• Solving ill-conditioned and singular linear systems (Pseudo-inverse)

• Dimensional reduction in Data analysis (PCA, EOF, POD analysis)

• and more...

Because of its ubiquity in computational linear algebra and data science. we will spend a bit of time to understand the SVD and its applications (but not the specific algorithms). But first

Fundamentals¶

Objectives

• Understand basic linear-algebraic operations and their computational costs

• Understand Numpy implementation (and performance) for Linear Algebra

• Understand Singular vs Invertible matrices

• Understand Orthonormal vectors and $Q$ matrices

• Understand vector and Matrix norms

• Understand the Condition Number

Matrix-Vector Multiplication¶

One of the most basic operations we can perform with matrices is to multiply them by a vector which maps a vector to a vector. There are multiple ways to interpret and compute the matrix-vector product $A \mathbf{x}$.

index notation¶

row picture (dot products)¶

We can also consider matrix-vector multiplication as a sequence of inner products (dot-products between the rows of $A$ and the vector $\mathbf{x}$.

where $\mathbf{a}_i^T$ is the $i$th row of $A$

column picture¶

An alternative (and entirely equivalent way) to write the matrix-vector product is as a linear combination of the columns of $A$ where each column’s weighting is $x_j$.

This view will be useful later when we are trying to interpret various types of matrices.

Operation Counts¶

No matter how you compute $A\mathbf{x}$, the total number of operations is the same (for a dense matrix $A$). The row view however is convenient for calculating the Operation counts required for $A\mathbf{x}$.

If $A\in\mathbb{C}^{m\times n}$ and $\mathbf{x}\in\mathbb{C}^n$. Then just counting the number of multiplications involved to compute $A\mathbf{x}$ is $O(??)$

One important property of the matrix-vector product is that is a linear operation, also known as a linear operator. This means that the for any $\mathbf{x}, \mathbf{y} \in \mathbb{C}^n$ and any $c \in \mathbb{C}$ we know that

1. $A (\mathbf{x} + \mathbf{y}) = A\mathbf{x} + A\mathbf{y}$

2. $A\cdot (c\mathbf{x}) = c A \mathbf{x}$

Example: Numerical matrix-vector multiply¶

Write a matrix-vector multiply function and check it with the appropriate numpy routine. Also verify the linearity of the matrix-vector multiply.

Check equivalence¶

first set up some large random matrices and vectors and compare to numpy built in .dot function

Check Linearity¶

Check Timing/performance¶

Matrix-Matrix Multiplication¶

The matrix product with another matrix $C=AB$ is defined as

i.e. each component of $C$ is a dot-product between the $i$th row of $A$ and the $j$th column of $B$

As with matrix-vector multiplication, Matrix-matrix multiplication can be thought of multiple ways

• $m\times p$ dot products (each with $n$ flops)

• $A$ multiplying the columns of $B$

  $$C = AB = \begin{bmatrix} A\mathbf{b}_1 & A\mathbf{b}_2 & \ldots & A\mathbf{b}_p\\ \end{bmatrix}$$

  (26)

• Linear combinations of the rows of $B$

  $$C = AB = \begin{bmatrix} \mathbf{a}_1^T B \\ \mathbf{a}_2^T B \\ \vdots \\ \mathbf{a}_m^T B\\ \end{bmatrix}$$

  (27)

Questions¶

• What are the dimensions of $A$ and $B$ so that the multiplication works?

• What are the Operations Counts for Matrix-Matrix Multiplication?

• Comment on the product $\mathbf{c}=(AB)\mathbf{x}$ vs. $\mathbf{d} = A(B\mathbf{x})$

Example: Outer Product¶

The product of two vectors $\mathbf{u} \in \mathbb{C}^m$ and $\mathbf{v} \in \mathbb{C}^n$ is a $m \times n$ matrix where the columns are the vector $u$ multiplied by the corresponding value of $v$: $$

$$

It is useful to think of these as operations on the column vectors, and an equivalent way to express this relationship is $$

$$

Or each column is just a scalar multiple of $\mathbf{u}$

Alternatively you can think of this as the rows are all just scalar multiples of $\mathbf{v}$

rank 1 updates¶

We call any matrix of the form $\mathbf{u}\mathbf{v}^T$ a “rank one matrix” ( because its rank r=?). These sort of matrix operations are very common in numerical algorithms for orthogonalization, eigenvalues and the original page-rank algorithm for google. Again, the order of operations is critical.

Comment on the difference in values and operation counts between

and

for $\mathbf{u}$, $\mathbf{v}$, $\mathbf{x}$, $\mathbf{y}$, $\tilde{\mathbf{y}}\in\mathbb{R}^n$,

Check¶

Set up some random vectors

Check Equivalence of numbers¶

show

Check Timing/performance¶

Example: Upper Triangular Multiplication¶

Consider the multiplication of a matrix $A \in \mathbb{C}^{m\times n}$ and the upper-triangular matrix $R$ defined as the $n \times n$ matrix with entries $r_{ij} = 1$ for $i \leq j$ and $r_{ij} = 0$ for $i > j$. The product can be written as

The columns of $B$ are then

so that $\mathbf{b}_j$ is the sum of the first $j$ columns of $A$.

Example: Write Matrix-Matrix Multiplication¶

Write a function that computes matrix-matrix multiplication and demonstrate the following properties:

1. $A (B + C) = AB + AC$ (for square matrices))

2. $A (cB) = c AB$ where $c \in \mathbb{C}$

3. $AB \neq BA$ in general

NumPy Products¶

NumPy and SciPy contain routines that are optimized to perform matrix-vector and matrix-matrix multiplication. Given two ndarrays you can take their product by using the dot function.

Check non-commutative property of matrix-matrix multiplication¶

It’s easy to demonstrate the non-commutative nature of Matrix-Matrix multiplication with almost any two matrices $A$ and $B$. For a clear demonstration, consider the two matrices $D$ a diagonal matrix and $A$ a matrix of all 1s

Range and Null-Space¶

Range¶

• The range of a matrix $A \in \mathbb R^{m \times n}$ (similar to any function), denoted as $\text{range}(A)$, is the set of vectors that can be expressed as $A x$ for $x \in \mathbb R^n$.

• We can also then say that that $\text{range}(A)$ is the space spanned by the columns of $A$. In other words the linearly independent columns of $A$ provide a basis for $\text{range}(A)$, also called the column space of the matrix $A$.

• $C(A)$ controls the existence of solutions to $A\mathbf{x}=\mathbf{b}$

Null-Space¶

• Similarly the null-space of a matrix $A$, denoted $\text{null}(A)$ is the set of vectors $\mathbf{x}$ that satisfy $A \mathbf{x} = \mathbf{0}$.

• $N(A)$ controls the uniqueness of solutions to $A\mathbf{x}=\mathbf{b}$

• A similar concept is the rank of the matrix $A$, denoted as $\text{rank}(A)$, is the dimension of the column space. A matrix $A$ is said to have full-rank if $\text{rank}(A) = \min(m, n)$. This property also implies that the matrix mapping is one-to-one.

Inverse¶

A non-singular or invertible matrix is characterized as a square matrix with full-rank. This is related to why we know that the matrix is one-to-one, we can use it to transform a vector $x$ and using the inverse, denoted $A^{-1}$, we can map it back to the original matrix. The familiar definition of this is

Since $A$ has full rank, its columns form a basis for $\mathbb{R}^m$ and the vector $\mathbf{b}$ must be in the column space of $A$.

There are a number of important properties of an invertible matrix $A$. Here we list them as the following equivalent statements

1. $A$ has a unique inverse $A^{-1}$ such that $A^{-1}A=AA^{-1}=I$

2. $\text{rank}(A) = m$

3. $\text{range}(A) = \mathbb{C}^m$

4. $\text{null}(A) = \mathbf{0}$

5. 0 is not an eigenvalue of $A$

6. $\text{det}(A) \neq 0$

Example: Properties of invertible matrices¶

Show that given an invertible matrix that the rest of the properties hold. Make sure to search the numpy packages for relevant functions.

Orthogonal Vectors and Matrices¶

Orthogonality is a very important concept in linear algebra that forms the basis of many of the modern methods used in numerical computations.

Two vectors are said to be orthogonal if their inner-product or dot-product defined as

Here we have shown the various notations you may run into (the inner-product is in-fact a general term for a similar operation for mathematical objects such as functions).

If $\langle \mathbf{x},\mathbf{y} \rangle = 0$ then we say $\mathbf{x}$ and $\mathbf{y}$ are orthogonal. The reason we use this terminology is that the inner-product of two vectors can also be written in terms of the angle between them where

and $||\mathbf{x}||_2$ is the Euclidean ($\ell^2$) norm of the vector $\mathbf{x}$, which we can interpret as the length of a vector.

We can write the 2-norm or length of a vector in terms of the inner-product as well as

The generalization of the inner-product to complex vector spaces is defined as

where $x_i^*$ is the complex-conjugate of the value $x_i$.

Orthonormality¶

Taking this idea one step further we can say a set of vectors $\mathbf{x} \in X$ are orthogonal to $\mathbf{y} \in Y$ if

If in addition

then they are also called orthonormal.

Note that we dropped the 2 as a subscript to the notation for the norm of a vector. Later we will explore other ways to define a norm of a vector other than the Euclidean norm defined above.

Another concept that is related to orthogonality is linear-independence. A set of vectors $\mathbf{x} \in X$ are linearly independent if $\forall \mathbf{x} \in X$ that each $\mathbf{x}$ cannot be written as a linear combination of the other vectors in the set $X$.

An equivalent statement is that given a set of $n$ vectors $\mathbf{x}_i$, the only set of scalars $c_i$ that satisfies

is if $c_i=0$ for all $i\in[1,n]$

Show that if a set of vectors are orthonormal, they must be linearly independent.

This can be related directly through the idea of projection. If we have a set of vectors $\mathbf{x} \in X$ we can project another vector $\mathbf{v}$ onto the vectors in $X$ by using the inner-product. This is especially powerful if we have a set of orthogonal vectors $X$, which are said to span a space (or provide a basis for a space), s.t. any vector in the space spanned by $X$ can be expressed as a linear combination of the basis vectors $X$

Note if $\mathbf{v} \in X$ that

Looping back to matrices, the column space of a matrix is spanned by its linearly independent columns. Any vector $v$ in the column space can therefore be expressed via the equation above.

Unitary Matrices¶

A special class of matrices are called unitary matrices when complex-valued and orthogonal when purely real-valued if the columns of the matrix are orthonormal to each other. Importantly this implies that for a unitary matrix $Q$ we know the following

1. $Q^*Q = I$

2. therefore if $Q$ is square, $Q^* = Q^{-1}$

where $Q^*$ is called the adjoint (or Hermitian) of $Q$. The adjoint is defined as the transpose of the original matrix with the entries being the complex conjugate of each entry as the notation implies. Note, if $Q\in\mathbb{R}^{n\times n}$ then $Q^*=Q^T$

As an example if we have the matrix

The important part of being an unitary matrix is that the projection onto the column space of the matrix $Q$ preserves geometry in an Euclidean sense, i.e. preserves the Cartesian distance.

Vector and Matrix Norms and the condition number¶

The following sections will lay out the definitions and computation required to calculate a range of vector and matrix norms which provide a measure of the “size” of an object or the distance in some vector space.

In the context of Numerical Linear algebra, norms are essential for defining a key property of a matrix, the “condition number”.

In infinite precision, a square matrix is either invertible or singular, however, in finite precision, even an invertible matrix can behave poorly if it is ‘ill-conditioned’, i.e. it is almost singular.

We need a quantitiative measure of how “near-singular” a matrix is

Why not the Determinant $|A|$?¶

We know that if a matrix $A$ is singular, $|A|=0$. But what if $|A|$ is small?

Turns out even a perfectly invertible, well-conditioned matrix can have arbitrarily small determinant.

Consider the two diagonal matrices

by definition, $|I|=1$, but $|\epsilon I| = ??$.

More generally if $I\in\mathbb{R}^{n\times n}$, $|\epsilon I| = ??$.

Yet all these matrices are diagonal and easily inverted (i.e. $(\epsilon I )^{-1} = (1/\epsilon) I$). Thus we need something better (the condition number). But to get there requires developing important ideas about vector and matrix norms.

Vector Norms¶

Norms (and also measures) provide a means for measure the “size” or distance in a space. In general a norm is a function, denoted by $||\cdot||$, that maps $\mathbb{C}^m \rightarrow \mathbb{R}$. In other words we stick in a multi-valued object and get a single, real-valued number out the other end.

All norms satisfy the properties:

1. $||\mathbf{x}|| \geq 0$

2. $||\mathbf{x}|| = 0$ only if $\mathbf{x} = \mathbf{0}$

3. $||\mathbf{x} + \mathbf{y}||\leq ||\mathbf{x}|| + ||\mathbf{y}||$ (triangle inequality)

4. $||c \mathbf{x}|| = |c|||\mathbf{x}||$ where $c \in \mathbb{C}$

There are a number of relevant norms that we can define beyond the Euclidean norm, also know as the 2-norm or $\ell_2$ norm:

• $\ell_1$ norm:

  $$||\mathbf{x}||_1 = \sum^m_{i=1} |x_i|,$$

  (48)

• $\ell_2$ norm:

  $$||\mathbf{x}||_2 = \left( \sum^m_{i=1} |x_i|^2 \right)^{1/2},$$

  (49)

• $\ell_p$ norm:

  $$||\mathbf{x}||_p = \left( \sum^m_{i=1} |x_i|^p \right)^{1/p}, \quad \quad 1 \leq p < \infty,$$

  (50)

• $\ell_\infty$ norm:

  $$||\mathbf{x}||_\infty = \max_{1\leq i \leq m} |x_i|,$$

  (51)

1. weighted $\ell_p$ norm:

   $$||\mathbf{x}||_{W_p} = \left( \sum^m_{i=1} |w_i x_i|^p \right)^{1/p}, \quad \quad 1 \leq p < \infty,$$

   (52)

These are also related to other norms denoted by capital letters ($L_2$ for instance). In this case we use the lower-case notation to denote finite or discrete versions of the infinite dimensional counterparts.

Example: Comparisons Between Norms¶

Compute the norms given some vector $\mathbf{x}$ and compare their values. Verify the properties of the norm for one of the norms.

Geometric Interpretation¶

For every $p-$norm we can define a set of ‘unit vectors’ that is the set of all vectors in $\mathbb{R}^n$ with $||\mathbf{x}||_p = 1$.

For example in $\mathbb{R}^2$, the unit spheres in the 1-,2- and $\infty$-norm look like

And if $\mathbf{x} = \begin{bmatrix} 1 \\ 1 \\ \end{bmatrix}$ then $||\mathbf{x}||_1 = ??,~~$ $||\mathbf{x}||_2 = ??,~~$ and $||\mathbf{x}||_\infty = ??$

Induced Matrix Norms¶

The most direct way to consider a matrix norm is one induced by a vector-norm. Given a vector norm, we can define a matrix p-norm as the smallest number $C$ that satisfies the inequality

or as the supremum of the ratios so that

with no loss of generality, we can restrict $\mathbf{x}$ to the set of all unit vectors $||\mathbf{x}||_p=1$ and interpret the matrix p-norm as the maximum distortion of the “unit sphere”

Properties of all Matrix Norms (induced and non-induced)¶

In general matrix-norms have the following properties whether they are induced from a vector-norm or not:

1. $||A|| \geq 0$ and $||A|| = 0$ only if $A = 0$

2. $||A + B|| \leq ||A|| + ||B||$ (Triangle Inequality)

3. $||c A|| = |c| ||A||$

In addition, all induced p-norms satisfy the product rules

1. $||AB|| \leq ||A||\,||B||$

2. $||A\mathbf{x}|| \leq ||A||\,||\mathbf{x}||$

Computation of induced matrix p-norms¶

With a little work it can be shown that

1. $||A||_1$ = numpy.linalg.norm(A, ord=1) is the maximum 1-norm of the Columns of $A$

2. $||A||_2$ = numpy.linalg.norm(A, ord=2) = max(numpy.linalg.svd(A)[1] is the maximum Singular Value of $A$

3. $||A||_\infty$ = numpy.linalg.norm(A, ord=numpy.inf) is the maximum 1-norm of the Rows of $A$ (or $||A^T||_1$)

Examples¶

The Identity Matrix $||I||$¶

$||I||_1=||I||_2=||I||_\infty = ??$

Diagonal Matrices $||D||$¶

$||D||_1=|D||_2=||D||_\infty = ??$

Orthogonal Matrices $||Q||_2$ where $Q^*Q=I$¶

A fundamental property of $Q$ matrices is that they do not change the Euclidean length of vectors i.e.

Therefore

Example: Induced Matrix Norms¶

Consider the matrix

Compute the induced-matrix norm of $A$ for the vector norms $\ell_2$ and $\ell_\infty$.

$\ell^2$: For both of the requested norms the unit-length vectors $[1, 0]$ and $[0, 1]$ can be used to give an idea of what the norm might be and provide a lower bound.

computing each of the norms we have

which translates into the norms $||A \cdot [1, 0]^T||_2 = 1$ and $||A \cdot [0, 1]^T||_2 = 2 \sqrt{2}$. This implies that the $\ell_2$ induced matrix norm of $A$ is at least $||A||_{2} = 2 \sqrt{2} \approx 2.828427125$.

The exact value of $||A||_2$ can be computed using the spectral radius defined as

where $\lambda_i$ are the eigenvalues of $A$. With this we can compute the $\ell_2$ norm of $A$ as

Computing the norm again here we find

which has eigenvalues

so $||A||_2 \approx 2.9208096$.

The actual induced 2-norm of a matrix can be derived using the Singular Value Decomposition (SVD) and is simply the largest singular value $\sigma_1$.

Proof: Given that every Matrix $A\in\mathbb{C}^{m\times n}$ can be factored into its SVD (see notebook 10.1):

where $U\in\mathbb{C}^{m\times m}$ and $V\in\mathbb{C}^{n\times n}$ are unitary matrices with the property $U^*U=I$ and $V^*V=I$ (of their respective sizes) and $\Sigma$ is a real diagonal matrix of singular values $\sigma_1 \geq\sigma_2\geq...\sigma_n\geq 0$.

Then the 2-norm squared of a square matrix is

but $A^*A = V\Sigma^2V^*$ so

but if $||\mathbf{x}||_2 = 1$ (i.e. is a unit vector), then so is $\mathbf{y}$ because unitary matrices don’t change the length of vectors. So it follows that

Some Quick proofs¶

The induced 1-norm is the max of the 1-norm of the columns of $A$

Given

where $||\mathbf{x}||_1 = 1$. Then