linear-algebra-and-numerical-analysis

Intro to linear algebra

Spans and linear combinations

A linear combination of two vectors ($\vec v$, $\vec w$) is, where (a,b) are scalars:

$a\vec v + b\vec w$

The span of two vectors $\vec{v}$ and $\vec{w}$ is the set of all their linear combinations.

• In 2D, two non-collinear vectors typically span the whole plane.
• If two vectors line up (one is a scalar multiple of the other), they span only a line.

Based on span, we have the concept of linear dependence vs independence:

• Linearly dependent: one vector can be expressed as a linear combination of others (redundant).
• Linearly independent: no vector in the set is redundant.

Checking for linear independence

Given two vectors $\vec x$ and $\vec y$, you test for linear independence by setting their linear combination equal to the zero vector.

$c_1 \vec x + c_2 \vec y = \vec 0$

• If the only solution is that both $\vec x$ and $\vec y$ are $\vec 0$, then they are linearly dependent.
• If there is a solution with either $\vec x$ and $\vec y$ not being the zero vector, then they are linearly dependent.

Matrices as linear transformations

A matrix has its columns as basis vectors, and applies a transformation to vectors by using the matrix's basis vectors as the basis vectors for the vector it wants to transform, mapping that vector into the matrix's coordinate space.

Here is how a matrix $A$ translates a vector $\vec x$ in standard coordinate space (basis vectors are $\vec i$ and $\vec j$) into a vector $\vec v$.

$A\vec x = \vec v$

NOTE

$A\vec x = \vec b$ has a solution if $\vec b$ is in the span of the columns of $A$.

You can describe a linear transformation by just recording what happens to the $\hat i$ and $\hat j$ basis vectors of the original coordinate space and how they get transformed.

For example, if a linear transformation scales $\hat i$ to $2 \hat i$, then the matrix representation of the linear transformation is $\begin{matrix} 2 & 0 \\ 0 & 1 \end{matrix}$, or $[2 \hat i^T, \hat j^T]$

For this example, let's assume $A = \begin{matrix} 2 & 0 \\ 0 & 1 \end{matrix}$ and $\vec x = \begin{matrix} -7 \\ 5 \end{matrix}$.

1. The basis vectors of $A$, let's call them $\hat a_1 = \begin{matrix} 2 \\ 0 \end{matrix}$ and $\hat a_2 = \begin{matrix} 0 \\ 1 \end{matrix}$
2. When we transform $\vec x$ into the coordinate space of $A$, basically we're going to change the linear combination representation of $\vec x$ from using the standard coordinate space basis vectors ($\hat i$ and $\hat j$) to the basis vectors of $A$:

$\vec x = \begin{matrix} -7 \\ 5 \end{matrix} = -7 \hat i + 5 \hat j$

$A \vec x = -7 \hat a_1 + 5 \hat a_2 = \begin{matrix} -7 \\ 5 \end{matrix}$

3. But this $\begin{matrix} -7 \\ 5 \end{matrix}$ is now in the "language" of the non-standard basis vectors $\hat a_1$ and $\hat a_2$, and the only way for us to understand what truly happened to $\vec x$ is to translate the basis vectors into the standard coordinate space and then rewrite everything as a linear combination in the standard space:

$A \vec x = -7 \hat a_1 + 5 \hat a_2 = -7 \begin{pmatrix} 2 \\ 0 \end{pmatrix} + 5 \begin{pmatrix} 0 \\ 1 \end{pmatrix} = \begin{matrix} -14 \\ 5 \end{matrix} = \vec v$

Matrix multiplication properties

• Not commutative: (AB \ne BA) in general.
• Associative: (A(BC)=(AB)C).
• applied right to left: Applying one transformation after another is composition. If you first apply (B) then apply (A), the combined transformation is (AB), because matrix multiplication is applied right to left.

Change of basis

Let's assume

Determinants and invertible matrices

The geometric meaning of a determinant

For a 2×2 matrix, ($|\det(A)|$) is how much areas scale.

• ($|\det(A)| > 1$): areas expand
• ($0 < |\det(A)| < 1$): areas shrink
• ($\det(A) < 0$): orientation flips (a “mirror”/reflection component)

But what if the determinant is 0, meaning the basis vectors are collinear with each other? That's where determinants connect to linear independence and dependence and singular matrices:

• $\det(A)=0$: space gets “squished” into a lower dimension (e.g., plane → line).
  • linearly dependent: basis vectors become linearly dependent.
  • singular: since the columns of the matrix (basis vectors) are linearly dependent, matrix is singular.
• $\det(A) \ne 0$: the parallelogram formed by the basis vectors has non-zero area
  • linearly dependent: basis vectors are not collinear, since that is the only way for the parallelogram formed by the basis vectors to have non-zero area
  • singular: since the columns of the matrix (basis vectors) are linearly dependent, matrix is singular.

Mathematical properties of determinants

• multiplicative rule: if a matrix $B$ gets transformed via composition by matrix $A$, then the area formed by its basis vectors ($\det(b)$) gets scaled by the area formed from the basis vectors of $A$, namely $\det(a)$.

  $$det(AB) = det(A) \cdot det(B)$$

• inverse rule

  $$det(A^{-1}) = \frac{1}{det(A)}$$

• additive rule

  $$det(A-B) = det(A) - det(B)$$

Invertible and singular matrices

To represent a system of equations, you can use a coefficient matrix, multiply it by a variable vector, and set it equal to a constants vector: $A\vec{x}=\vec{v}$.

In plain english:

We are looking for a vector $\vec{x}$ that when transformed by $A$, lands on $\vec{v}$.

To solve this system of equations, we can use inverse matrices: Inverse matrices are the inverse transformation of a matrix.

By applying a transformation, then subsequently applying the inverse of that transformation, you end up back where you started: $A^{-1}A=I$.

• If a matrix rotates space clockwise by 90 degrees, an inverse matrix of that matrix would rotate space counterclockwise 90 degrees.
• doing a transformation $A$ then doing the transformation $A^{-1}$ is the same thing as doing nothing.

By using the inverse, you can find the variable vector like so

$\vec{x} = A^{-1} \vec{v}$

A matrix is invertible/nonsingular if it has an inverse, else we call it singular if it does not have an inverse.

Singular matrices are noninvertible (have det = 0) while nonsingular matrices are invertible. In terms of G.E, this means the following:

• singular matrices: infinite solutions or no solutions. One row is just full zeros when reduced via G.E, so there is at least one free variable.
• nonsingular: Has one solution for $A \vec x = \vec b$, meaning there is a pivot in each row and along the diagonals in its correct spot.

when matrices don’t have an inverse

If the determinant of matrix is 0, then it does not have an inverse because it squishes all of space onto one line irreversibly. The area of the parallelogram formed by the basis vectors is 0. You cannot un-squish a line.

Also, a matrix transformation being injective and surjective plays a role in if its invertible or not.

• injective: A linear map is injective iff the only vector mapped to (0) is the zero vector.
  • Basically, no transformed vector besides the zero vector should transform to the zero vector, otherwise the linear transformation is not injective.
• surjective: Once transformed, the new basis matrix has the same span as the original basis matrix. Basically, the transformation matrix must be full rank and a square matrix.

Transformation matrices will only have inverses if they are bijective - meaning both injective and surjective.

So in summary, here are the three cases where a transformation matrix $M$ will not have an inverse:

1. $det(M) = 0$: transformation matrix is not injective, because some vectors will get squished to the zero vector as a result of this transformation.
2. nonsquare matrices: Not surjective, since their column space is not full rank.
3. matrices that transform some vectors to the $\vec 0$: These matrices are not injective by definition.

Rank, column space, null space

• Rank: number of dimensions in the output / the dimension of the column space.
• Column space: the span of the columns of ($A$).
• null space: The null space is all vectors mapped to zero, which can be found through this equation:

$A\vec x = \vec 0$

rank

rank means the number of dimensions in the output of the transformation, and is used to differentiate between transformations that either take up all the possible dimensions or have a zero-determinant and thus squish all vectors into a lower dimension.

• When the output of a transformation is a line, the rank is 1.
• When the output of a transformation is a plane, the rank is 2.
• When the output of a transformation is all of space, the rank is 3.
• Full rank means that the number of dimensions matches the number of columns.
  • example: full rank for an $\mathbb{R}^4$ space is 4.

IMPORTANT

Matrices are full rank iff they are injective, meaning its null space only has the trivial solution $\vec x = \vec 0$.

column space

Column space is the span of the columns of the matrix, with the max column space for a $m \times n$ matrix being $\mathbb{R}^n$.

• when a matrix is singular based on column space: If your column space dimensions are less than the dimensions of the matrix, meaning less dimensional than $\mathbb{R}^n$ , then the matrix is singular.

null space

The null space is the set of all possible vectors that become null, or $\vec 0$ after a linear transformation.

Geometrically, it's the set of all vectors that land on the origin after a linear transformation, and has two types of solutions:

• trivial solution: the only vector that maps to the origin is the origin itself, $\vec 0$, since by nature of a linear transformation the origin (zero vector) always stays fixed.
• nontrivial solution: there is a non-empty set of non-zero vectors called the kernel that gets transformed into the $\vec 0$.

You can find the null space by solving a system of equations and setting the post-transformed vector to the $\vec 0$.

$$A\vec x = \vec 0$$

NOTE

The kernel is the set of all solutions to the null space equation, and a trivial solution leads to a trivial kernel, and a nontrivial solution leads to a nontrivial kernel.

Cramer's rule

Cramer's rule comes into play when we have an equation $A \vec x = \vec b$, where $A$ and $\vec b$ are known, and we want to find out what $\vec x = \begin{pmatrix} x \\ y \end{pmatrix}$ is.

Intuition

Consider that for the standard identity matrix with basis vectors $\hat i$ and $\hat j$, we can represent the coordinates of a vector $\vec x = \begin{pmatrix} x \\ y \end{pmatrix}$ as two areas.

Let's form the following notation:

• $\text{Area}_{\hat i, \vec x}$: the area of the parallelogram formed by $\vec x$ and $\hat i$
• $\text{Area}_{\vec x, \hat j}$: the area of the parallelogram formed by $\vec x$ and $\hat j$

Let's dive into the calculations

• $x$: the area of the parallelogram formed by $\vec x$ and $\hat j$ turns out to be $x \hat j$.

$x = x \hat j = \det([ \vec x, \hat j]) = x \det(I) = \text{Area}_{\vec x, \hat j}$

• $y$: the area of the parallelogram formed by $\vec x$ and $\hat i$ turns out to be $y \hat i$.

$y = y \hat j = \det([ \hat i, \vec x]) = y \det(I) = \text{Area}_{\hat i, \vec x}$

Now that we found what $x$ and $y$ are in terms of basis vectors, we can swap those standard basis vectors out for any matrix, and understand that linear transformations $A$ will scale and stretch vectors evenly:

$det(AB) = det(A)det(B)$

• $\text{Area}_{\hat i, \vec x} = y \cdot \det(I) = y$, but after transformation from A, it becomes $y \det(A)$, and now find the signed area using the output vector $\vec b$, since $A\vec x = \vec b$, thus we deal with $\vec b$ instead of $\vec x$ in the transformed coordinate space of $A$ and luckily since we know $\vec b$, thus we arrive at this new formula:

$y = \frac{\text{Area}_{\hat a_1, \vec b}}{\det(A)}$

• $\text{Area}_{\vec x, \hat j} = x \cdot \det(I) = x$, but after transformation from A, it becomes $x \det(A)$, and now find the signed area using the output vector $\vec b$, since $A\vec x = \vec b$, thus we deal with $\vec b$ instead of $\vec x$ in the transformed coordinate space of $A$ and luckily since we know $\vec b$, thus we arrive at this new formula:

$x = \frac{\text{Area}_{\vec b, \hat j}}{\det(A)}$

Dot product

For two vectors $\vec v$ and $\vec w$, the dot product $\vec v \cdot \vec w$ can be thought of as the length of projected $\vec w$ on $\vec v$ times the length of $\vec v$

• When two vectors point in generally the same direction, their dot product is positive
• Whe two vectors point in generally the opposite directions, their dot product is negative.

This is another formula for the dot product that lets you find the angle between two vectors:

$\vec{a} \cdot \vec{b} = \|\vec a\|\|\vec b\|cos{\theta}$

Geometric interpretation

For two vectors $\vec v$ and $\vec w$, the dot product $\vec v \cdot \vec w$ can be thought of as the length of projected $\vec w$ on $\vec v$ times the length of $\vec v$.

Here's how to geometrically visualize $\vec v \cdot \vec w$ and $\vec w \cdot \vec v$:

1. Think that you are projecting $\vec w$ onto $\vec v$, so draw a line down from the tip of $\vec w$ towards $\vec v$ until you hit $\vec v$, and that line should form a right triangle, with $\vec v$ and $\vec w$.

2. Now multiply the length of the projected $\vec w$ onto $\vec v$ by the length of $\vec v$ to achieve the dot product $\vec v \cdot \vec w$.

3. Notice that this operation is commutative, where $\vec w \cdot \vec v$ yields the same result, even though now we're projecting $\vec v$ onto $\vec w$ instead. This is because both geometric interpretations are exact mirror opposites of each other.

4. Even with scalar multiplication that breaks symmetry, the overall effect is still the same if you go through the math:
   • $2\vec v \cdot \vec w$: The length of $\vec w$ projected onto $2\vec v$ doesn't change, but we now multiply by $\| 2 \vec v \|$, which doubles the dot product.
   • $\vec w \cdot 2\vec v$: The length of $2 \vec v$ projected onto $\vec w$ does change, but it approximately doubles the length of the previous projection of $\vec v$ onto $\vec w$, so the overall effect still doubles the dot product.

Now let's understand how this geometric interpretation works with other cases:

• vectors point in roughly same direction: results in a positive length
• vectors point in roughly opposite directions: results in a negative length

• vectors are perpendicular: geometrically, to form a projection you draw a line straight down from the tip of the vector you're trying to project onto the other vector. You can't do it if they're perpendicular, which is why the dot product is zero if the vectors are perpendicular, Because there's no way to draw a projection from one vector onto another if the vectors are perpendicular

Algebraic duality interpretation

Great. Now we know that dot products correspond to projections but we need to understand why the mathematical way of just ordered coordinate pair multiplication of dot products actually corresponds to a projection.

The way we can view this is through duality, which considers vectors as linear transformations that squish space onto a lower dimension, namely a single number line:

• linear transformations that squish space onto a line have basis vectors land on a number in the number line.

Consider an example $\vec v = \begin{pmatrix} 4 \\ 3 \end{pmatrix}$ and $\vec w = \begin{pmatrix} 1\\ -2 \end{pmatrix}$, and we are doing $\vec w \cdot \vec v$, which has the duality interpretation of transforming $\vec v$ into the coordinate space (single number line) of $\vec w$ using the basis vectors of $\vec w$ being $\hat w_1 = 1$ and $\hat w_2 = -2$, so we can rewrite the dot product as a linear transformation which ends up being just a linear combination:

$\vec w \cdot \vec v = 4 \hat w_1 + 3 \hat w_2 = 4(1) + 3(-2) = -2$

Projections

Although the dot product may seem asymmetric since the vector you are projecting is different depending on which vector comes first in the dot product, in the end they both calculate out to be the exact same thing.

This allows us to find the lengths of the individual projections even if the dot product is the same.

Let's start off with some notation:

Orthonormal transformations

here's a thought: in the standard coordinate space, we can represent an arbitrary vector like so:

$\begin{pmatrix} x \\ y \end{pmatrix} = x \hat i + y \hat j = \begin{pmatrix} x \\ y \end{pmatrix} \cdot \begin{pmatrix} 1 \\ 0 \end{pmatrix} + \begin{pmatrix} x \\ y \end{pmatrix} \cdot \begin{pmatrix} 0 \\ 1 \end{pmatrix} = \begin{pmatrix} x \\ y \end{pmatrix} \cdot \hat i + \begin{pmatrix} x \\ y \end{pmatrix} \cdot \hat j$

So we would naively think that we can represent any vector $\vec x$ as the sum of its dot products with each basis vector of a matrix.

But that only works in one special case: orthonormal transformations.

Orthonormal transformations are those in which the dot product of two vectors is preserved even after the same matrix transformation is applied to those two vectors.

The only matrices $U$ that provide orthonormal transformations are of the orthogonal family of matrices, where vectors 1) are not stretched and 2) maintain the same angle.

More formally, matrices $U$ that provide orthonormal transformations must satisfy these two properties:

1. $det(U) = 1$: Because the basis vectors are uniform, transformed vectors are not stretched.

NOTE

So what does it really mean to have a matrix be representative of an orthonormal transformation?

Their rows and columns form orthonormal sets of vectors, which means they preserve the inner product of vectors, thus maintaining lengths and angles in complex vector spaces, which leads to the determinant having an absolute value of 1.

In the case of orthonormal transformations you can very easily find an input vector that results in a corresponding known output vector via these steps:

inner products vs outer products

Suppose you have two vectors of the same length, $x$ and $y$ such that $x, y \in \mathbb{R}^n$

• inner product: The inner product, also known as the dot product, is $x^T y$
• outer product: The outer product $xy^T$ produces an $n \times n$ matrix.

Cross product

The cross product of two vectors $\vec a$ and $\vec b$ measures the area of the parallelogram formed by those two vectors:

$$\vec a \times \vec b = \| \vec a \| \| \vec b \| \sin{\theta}$$

Here are the behaviors of a cross product:

• greatest when two vectors are orthogonal: This is because $\sin90 = 1$.
• $\vec a \times \vec a = 0$: this is because the angle between a vector and itself is 0, therefore $\sin 0 = 0$

Eigenvectors and Eigenvalues

Eigenvectors are simply vectors that stay on their span after a linear transformation. More formally, they satisfy the equation $A\vec v = \lambda \vec v$:

• Eigenvector: a vector $\vec v$ that stays on its own span after transformation.
• Eigenvalue: the factor $\lambda$ by which that eigenvector is scaled.
• Eigenpair: the pair of an eigenvector and its corresponding eigenvalue $(\lambda, \vec v)$

To compute eigenvalues, we can try to find the null space of $A\vec v - \lambda \vec v= \vec 0$, which will then give us all the eigenpairs possible.

So we start off with this:

$(A-\lambda I)\vec v = \vec 0$

If $(A - \lambda I)\vec v = \vec 0$, then $det(A-\lambda I) = 0$. Which then gives us the characteristic equation we can solve for as a polynomial:

$\det(A-\lambda I)=0$

NOTE

The reasoning is that the only way for a matrix times a vector to be the $\vec 0$ is if the matrix has a nontrivial null space and therefore is not full rank, and therefore the matrix is singular, therefore, the determinant of the matrix is 0.

You can now also use determinants to solve for eigenvectors and eigenvalues.

1. Solve the polynomial $det(A-\lambda I) = 0$ for all the possible $\lambda$
2. Plug in $\lambda$ into $A \vec v = \lambda \vec v$ to solve for the eigenvectors

Solving for eigenpairs

Here are the general steps:

1. Rewrite $A\vec v = \lambda \vec v$ to $A\vec v - \lambda \vec v = \vec 0$

2. Since comparing matrix-vector multiplication with scalar-vector multiplication is awkward, we can rewrite $\lambda$ as $\lambda I$, which will just put the eigenvalues $\lambda$ along the diagonal of the matrix.

   $$(A - \lambda I)\vec v = \vec 0$$

3. If $(A - \lambda I)\vec v = \vec 0$, then $det(A-\lambda I) = 0$. The reasoning is that the only way for a matrix times a vector to be the $\vec 0$ is if the matrix has a null space and is therefore non-invertible and therefore has a determinant = 0. Use this equation to find the eigenvalues.

4. Plug back in the eigenvalues you found when you solved for $\lambda$ back into the equation and solve for the eigenvectors:

   $$(A - \lambda I)\vec v = \vec 0$$

NOTE

A quick tip to find eigenvalues:

---

If $A - \lambda I$ produces a triangular matrix or a diagonal matrix, then the eigenvalues simply lie along the diagonal of $A - \lambda I$. Proof and intuition in [[#Diagonal matrices and eigenvalues]].

Eigenvalue theorems

proof: The determinant of a matrix $A$ is equal to product of its eigenvalues

Prove that the determinant of an $n \times n$ matrix $A$ equals the product of its eigenvalues because the determinant is precisely the constant term of the matrix's characteristic polynomial.

The determinant of a matrix $A$ is equal to product of its eigenvalues:

$$det(A) = \Pi_{i=1}^n \lambda_i$$

How do we prove this?

Proof via the Characteristic Polynomial

Every eigenvalue $\lambda$ of $A$ satisfies the characteristic equation:

$\det(\lambda I - A) = 0$

Let $p(\lambda) = \det(\lambda I - A)$. Because $A$ is an $n \times n$ matrix, $p(\lambda)$ is a monic polynomial of degree $n$. By the Fundamental Theorem of Algebra, $p(\lambda)$ can be factored completely over the complex numbers in terms of its $n$ roots (the eigenvalues $\lambda_1, \lambda_2, \dots, \lambda_n$, counted with multiplicity):

$p(\lambda) = (\lambda - \lambda_1)(\lambda - \lambda_2)\dots(\lambda - \lambda_n)$

Now, evaluate both representations of $p(\lambda)$ at $\lambda = 0$:

1. Determinant definition: $p(0) = \det(0 \cdot I - A) = \det(-A)$

   Factoring out the scalar $-1$ from all $n$ rows yields:

   $\det(-A) = (-1)^n \det(A)$

2. Factored roots definition: $p(0) = (0 - \lambda_1)(0 - \lambda_2)\dots(0 - \lambda_n) = (-1)^n \prod_{i=1}^{n} \lambda_i$

Equating the two expressions for $p(0)$:

$(-1)^n \det(A) = (-1)^n \prod_{i=1}^{n} \lambda_i$

Dividing both sides by $(-1)^n$ leaves:

$\det(A) = \prod_{i=1}^{n} \lambda_i$

---

Alternative Proof via Schur Decomposition

In numerical linear algebra, this result is often viewed through the Schur Decomposition ( a generalization of diagonalization), which states that any square matrix $A$ can be factored as:

$A = Q T Q^*$

where $Q$ is unitary ($Q^* Q = I$) and $T$ is upper triangular.

• The diagonal entries of $T$ ($t_{11}, t_{22}, \dots, t_{nn}$) are precisely the eigenvalues $\lambda_1, \dots, \lambda_n$ of $A$.

• Using the multiplicative property of determinants: $\det(A) = \det(Q)\det(T)\det(Q^*) = \det(Q Q^*)\det(T) = \det(I)\det(T) = \det(T)$

• Because $T$ is upper triangular, its determinant is simply the product of its diagonal entries:

  $\det(T) = \prod_{i=1}^{n} t_{ii} = \prod_{i=1}^{n} \lambda_i$

Both paths reach the same conclusion: if any eigenvalue $\lambda_k = 0$, the entire product collapses to zero, which is why a matrix with a zero eigenvalue is non-invertible.

Therefore, for any $n\times n$ matrix $A$:

$$\det(A)=\prod_{i=1}^n \lambda_i$$

NOTE

Coming from this theorem, if a matrix has an eigenvalue $\lambda = 0$, then it has a determinant = 0 and is thus noninvertible (the product of eigenvalues becomes 0, thus determinant becomes 0).

Diagonal matrices and eigenvalues

For both diagonal and triangular (upper or lower) matrices, the eigenvalues are simply the entries along the main diagonal.

NOTE

An intuitive look:

---

If a matrix is diagonal, the standard basis vectors are eigenvectors and diagonal entries are eigenvalues.

For both diagonal and triangular (upper or lower) matrices, the eigenvalues are simply the entries along the main diagonal.

Why This Holds

For any $n \times n$ upper triangular matrix $U$:

$U = \begin{pmatrix} u_{11} & u_{12} & \dots & u_{1n} \\ 0 & u_{22} & \dots & u_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \dots & u_{nn} \end{pmatrix}$

The eigenvalues are the roots of the characteristic equation $\det(\lambda I - U) = 0$.

Subtracting $U$ from $\lambda I$ yields another upper triangular matrix:

$\lambda I - U = \begin{pmatrix} \lambda - u_{11} & -u_{12} & \dots & -u_{1n} \\ 0 & \lambda - u_{22} & \dots & -u_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \dots & \lambda - u_{nn} \end{pmatrix}$

Because the determinant of any triangular (or diagonal) matrix is the product of its diagonal entries:

$\det(\lambda I - U) = (\lambda - u_{11})(\lambda - u_{22})\cdots(\lambda - u_{nn}) = 0$

Setting this polynomial to zero gives the roots directly:

$\lambda_1 = u_{11}, \quad \lambda_2 = u_{22}, \quad \dots, \quad \lambda_n = u_{nn}$

Since a diagonal matrix is merely a special case of a triangular matrix (where all off-diagonal elements are zero), the exact same rule applies.

---

Significance in Numerical Analysis

Finding the roots of a high-degree polynomial directly is computationally unstable and expensive for large matrices. Because triangular and diagonal matrices reveal their eigenvalues by inspection, nearly all numerical eigenvalue algorithms work by transforming a general matrix into one of these simpler forms via similarity transformations ($A \mapsto X^{-1} A X$), which preserve eigenvalues:

• Eigendecomposition ($A = X \Lambda X^{-1}$): Transforms a diagonalizable matrix into a pure diagonal matrix $\Lambda$, where the diagonal holds the eigenvalues and the columns of $X$ are the eigenvectors.
• Schur Decomposition ($A = Q T Q^*$): Transforms any square matrix using a unitary matrix $Q$ into an upper triangular matrix $T$ (Schur form). The eigenvalues are read directly off the diagonal of $T$.
• QR Algorithm: The workhorse method in numerical linear algebra; it iteratively applies QR factorizations to drive a general matrix toward upper triangular (or quasi-triangular) form so the eigenvalues can be read straight off the diagonal.

Algebraic matrix properties

Inverse and transpose proofs

These are general proofs that work with all square matrices:

proof 1

We want to prove:

$$(AB)^{-1} = B^{-1}A^{-1}$$

proof 2

We want to prove:

$$(AB)^T = B^TA^T$$

Vector and matrix norms

Vector norms

A vector norm is a function that transforms a vector of any size into a scalar.

A vector norm is only valid if it satisfies these four properties:

1. positive: the norm returns a positive real number
2. injective: the norm is 0 only if the input is $\vec 0$.
3. preservation of scalars: scalars in scalar multiplication can be taken out of the norm.
4. satisfies triangle inequality

There are three vectors norms:

• L1 norm: the sum of the absolute value of all the elements in the vector
• L2 norm: the magnitude of the vector
• infinity norm: the element with the maximum absolute value out of all the elements in the vector.

1 norm

The 1-norm is simply the sum of the absolute value of all the elements in the vector

$$\| \mathbf{x}\|_1 =\sum_{i=1}^{n} |x_i|$$

2 norm

The 2-norm is the most common vector norm, which is just the magnitude of the vector

$$\| \mathbf{x}\|_2 = \left( \sum_{i=1}^{n} x_i^2 \right)^{1/2}$$

infinity-norm

The infinity-norm is simply the maximum absolute value of the elements in the vector.

$$\|\mathbf{x}\|_\infty = \max_{1 \le i \le n} |x_i|$$

Norm comparisons

$$\| x \|_\infty \le \| x \|_2 \le \sqrt n \| x \|_\infty$$

Matrix norms

Matrix norm is a function that takes in a matrix and returns a single scalar value.

A matrix norm aggregates all the values inside it, and must have these properties:

Matrix norms measure how much a matrix can stretch a vector:

$$\|A\| = \max_{x\ne 0} \frac{\|Ax\|}{\|x\|}.$$

Common induced norms include $\|A\|_1, \|A\|_\infty, \|A\|_2$.

L2 Norm (Frobenius Norm)

For matrices, the L2 norm is just the sum of the squares of all the elements in the matrix, and then take the square root of that.

This norm is also called the Frobenius Norm.

np.linalg.norm(matrix) # returns frobenius norm of matrix

Special matrices

Diagonal matrices

Diagonal matrices have these three core properties:

• eigenvalues lie along the diagonal:
  • The product of the diagonals of a diagonal matrix is equal to the product of the eigenvalues.
  • the trace of a diagonal matrix is equal to the sum of the eigenvalues of the diagonal matrix.

$Tr(D) = \sum_{i = 0}^n \lambda_i$

• diagonal matrix exponents are just exponentiating the diagonal elements: This means it’s trivial to calculate something like $A^n$.

• matrix multiplication is commutative: If you have a diagonal matrix $D$ and a nondiagonal matrix $A$, then matrix multiplication is commutative with diagonal matrices.

  $$AD = DA$$

Diagonal proofs

determinant of a diagonal matrix is product of its diagonal elements and thus eigenvalues

A matrix’s determinant is equal to the product of its eigenvalues, so since diagonal elements in a diagonal matrix are the eigenvalues, the determinant of a diagonal matrix is equal to the product of its diagonal values.

Symmetric matrices

A symmetric matrix is a matrix that is equal to its transpose

$$A = A^T$$

• $A^2 = AA^T$

Orthogonal, unitary, and Hermitian matrices

Decompositions

Cholesky decomposition

Eigendecomposition

You can represent any $n \times n$ matrix $A$ with $n$ linearly independent eigenvectors as its eigendecomposition, which you can get by manipulating the eigenvector formula $Ax = \lambda x$, which only works for square and invertible matrices $A$.

Starting from a $n \times n$ invertible matrix $A$:

• $\lambda$: the diagonal matrix with eigenvalues of $A$ along the diagonal.
• $U$: the matrix of eigenvectors of $A$, which we often normalize to be unit vectors.
• $\Lambda$: the diagonal matrix with the corresponding eigenvalues of $U$ along the diagonal, gotten from the neat trick of $\Lambda = \lambda I$

Here are the steps:

1. Find the eigenpairs of $A$
2. We can form the matrix $U$ as the matrix whose columns are the eigenvectors of $A$.
3. From the standard eigenvector equation $A \vec v = \lambda \vec v$, that corresponds to the matrix version $A U = U \Lambda$ , where $\Lambda = \lambda I$, the diagonal matrix with the corresponding eigenvalues of $U$ along the diagonal.
4. Multiply both sides by $U^{-1}$

From these to steps, we arrive this equation:

$$A = U\lambda U^{-1}$$

Similarity transforms, diagonalization, and Schur

Similarity transform

$$B = S^{-1}AS$$

• Same eigenvalues.
• Same determinant, trace, characteristic polynomial.

Diagonalization (special case)

If $A$ has $n$ independent eigenvectors:

$$A = P D P^{-1}$$

Schur decomposition (more general)

Every square matrix has a Schur form (over complex numbers):

$$A = Q T Q^*$$

where $Q$ is unitary and $T$ is upper triangular.

Numerical relevance:

• Many eigenvalue algorithms are based on Schur form because it’s stable.