MATH347DS

MATH347DS L07: Row-echelon form, determinants, eigendecomposition

Overview

Reduction to echelon form
Determinants
Eigenvalues, eigenvectors

Row-echelon, column echelon forms

Form a lower triangle of zeros by row Gauss elimination to obtain row echelon form
- left-most non-zero component on a non-zero row is to the right of non-zero entry of rows above, e.g.
- if all leading non-zero entries are 1, matrix is in reduced row echelon form.
$𝑨 = [\begin{array}{lllll} 1 & 0 & 3 & 0 & 5 \\ 0 & 1 & 4 & 1 & 2 \\ 0 & 0 & 0 & 1 & 3 \end{array}]$

Form an upper triangle of zeros by column Gauss elimination to obtain column echelon form

Determinants

Definition. The determinant of a square matrix $𝑨 = (\begin{array}{lll} 𝒂_{1} & \dots & 𝒂_{m} \end{array}) \in ℝ^{m \times m}$ is a real number

$\det (A) = | \begin{array}{cccc} a_{11} & a_{12} & \dots & a_{1 m} \\ a_{21} & a_{22} & \dots & a_{2 m} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ a_{m 1} & a_{m 2} & \dots & a_{m m} \end{array} | \in ℝ$

giving the (oriented) volume of the parallelepiped spanned by matrix column vectors.

$m = 2$
$𝑨 = (\begin{array}{cc} a_{11} & a_{12} \\ a_{21} & a_{22} \end{array}),, \det (𝑨) = | \begin{array}{cc} a_{11} & a_{12} \\ a_{21} & a_{22} \end{array} |$
$m = 3$
$𝑨 = (\begin{array}{ccc} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{array}),, \det (𝑨) = | \begin{array}{ccc} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{array} |$

Determinants of dimensions 2,3

Computation of a determinant with $m = 2$
$| \begin{array}{cc} a_{11} & a_{12} \\ a_{21} & a_{22} \end{array} | = a_{11} a_{22} - a_{12} a_{21}$
Computation of a determinant with $m = 3$
$\begin{array}{rcl} | \begin{array}{ccc} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{array} | & = & a_{11} a_{22} a_{33} + a_{21} a_{32} a_{13} + a_{31} a_{12} a_{23} \\ - a_{13} a_{22} a_{31} - a_{23} a_{32} a_{11} - a_{33} a_{12} a_{21} \end{array}$
Where do these determinant computation rules come from? Two viewpoints
- Geometric viewpoint: determinants express parallelepiped volumes
- Algebraic viewpoint: determinants are computed from all possible products that can be formed from choosing a factor from each row and each column

Determinant in 2D gives area of parallelogram

$m = 2$

Figure 1.
In two dimensions a “parallelepiped” becomes a parallelogram with area given as
$(Area) = (Length of Base) \times (Length of Height)$
Take $𝒂_{1}$ as the base, with length $b = || 𝒂_{1} ||$ . Vector $𝒂_{1}$ is at angle $φ_{1}$ to $x_{1}$ -axis, $𝒂_{2}$ is at angle $φ_{2}$ to $x_{2}$ -axis, and the angle between $𝒂_{1}$ , $𝒂_{2}$ is $θ = φ_{2} - φ_{1}$ . The height has length
$h = || 𝒂_{2} || \sin θ = || 𝒂_{2} || \sin . (. φ_{2} - φ_{1}) = || 𝒂_{2} || (\sin φ_{2} \cos φ_{1} - \sin φ_{1} \cos φ_{2})$
Use $\cos φ_{1} = a_{11} / || 𝒂_{1} ||$ , $\sin φ_{1} = a_{12} / || 𝒂_{1} ||$ , $\cos φ_{2} = a_{21} / || 𝒂_{2} ||$ , $\sin φ_{2} = a_{22} / || 𝒂_{2} ||$
$(Area) = || 𝒂_{1} || || 𝒂_{2} || (\sin φ_{2} \cos φ_{1} - \sin φ_{1} \cos φ_{2}) = a_{11} a_{22} - a_{12} a_{21}$

Determinant in 3D gives volume of parallelepiped

Determinant in 3D gives volume of parallelepiped

Figure 2.

The volume is (area of base) $\times$ (height) and given as the value of the determinant

\det (A) = | \begin{array}{ccc} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{array} |

Determinant calculations

The geometric interpretation of a determinant as an oriented volume is useful in establishing rules for calculation with determinants:
- Determinant of matrix with repeated columns is zero (since two edges of the parallelepiped are identical). Example for $m = 3$
  $Δ = | \begin{array}{ccc} a & a & u \\ b & b & v \\ c & c & w \end{array} | = a b w + b c u + c a v - u b c - v c a - w a b = 0$
  This is more easily seen using the column notation
  $Δ = \det (\begin{array}{cccc} 𝒂_{1} & 𝒂_{1} & 𝒂_{3} & \dots \end{array}) = 0$
- Determinant of matrix with linearly dependent columns is zero (since one edge lies in the 'hyperplane' formed by all the others)

Determinant calculation rules

Separating sums in a column (similar for rows)
$\det (\begin{array}{cccc} 𝒂_{1} + 𝒃_{1} & 𝒂_{2} & \dots & 𝒂_{m} \end{array}) = \det (\begin{array}{cccc} 𝒂_{1} & 𝒂_{2} & \dots & 𝒂_{m} \end{array}) + \det (\begin{array}{cccc} 𝒃_{1} & 𝒂_{2} & \dots & 𝒂_{m} \end{array})$
with $𝒂_{i}, 𝒃_{1} \in ℝ^{m}$
Scalar product in a column (similar for rows)
$\det (\begin{array}{cccc} α 𝒂_{1} & 𝒂_{2} & \dots & 𝒂_{m} \end{array}) = α \det (\begin{array}{cccc} 𝒂_{1} & 𝒂_{2} & \dots & 𝒂_{m} \end{array})$
with $α \in ℝ$
Linear combinations of columns (similar for rows)
$\det (\begin{array}{cccc} 𝒂_{1} & 𝒂_{2} & \dots & 𝒂_{m} \end{array}) = \det (\begin{array}{cccc} 𝒂_{1} & α 𝒂_{1} + 𝒂_{2} & \dots & 𝒂_{m} \end{array})$
with $α \in ℝ$ .

Determinant expansion

A determinant of size $m$ can be expressed as a sum of determinants of size $m - 1$ by expansion along a row or column
$\begin{array}{rcl} | \begin{array}{ccccc} a_{11} & a_{12} & a_{13} & \dots & a_{1 m} \\ a_{21} & a_{22} & a_{23} & \dots & a_{2 m} \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ a_{m 1} & a_{m 2} & a_{m 3} & \dots & a_{m m} \end{array} | & = & a_{11} | \begin{array}{cccc} a_{22} & a_{23} & \dots & a_{2 m} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ a_{m 2} & a_{m 3} & \dots & a_{m m} \end{array} | - \\ a_{12} | \begin{array}{cccc} a_{21} & a_{23} & \dots & a_{2 m} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ a_{m 1} & a_{m 3} & \dots & a_{m m} \end{array} | + \\ a_{13} | \begin{array}{ccccc} a_{21} & a_{22} & a_{24} & \dots & a_{2 m} \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ a_{m 1} & a_{m 2} & a_{m 4} & \dots & a_{m m} \end{array} | - \\ \dots \\ + {(- 1)}^{m + 1} a_{1 m} | \begin{array}{cccc} a_{21} & a_{23} & \dots & a_{2, m - 1} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ a_{m 1} & a_{m 3} & \dots & a_{m, m - 1} \end{array} | \end{array}$

Algebraic definition of determinant

The formal definition of a determinant
$\det A = \sum_{σ \in Σ} ν (σ) a_{1 i_{1}} a_{2 i_{2}} \dots a_{m i_{m}}$
requires $m m!$ operations, a number that rapidly increases with $m$
A more economical determinant is to use row and column combinations to create zeros and then reduce the size of the determinant, an algorithm reminiscent of Gauss elimination for systems

Example:
$| \begin{array}{ccc} 1 & 2 & 3 \\ - 1 & 0 & 1 \\ - 2 & - 1 & 4 \end{array} | = | \begin{array}{ccc} 1 & 2 & 3 \\ 0 & 2 & 4 \\ 0 & 3 & 10 \end{array} | = | \begin{array}{cc} 2 & 4 \\ 3 & 10 \end{array} | = 20 - 12 = 8$
The first equality comes from linear combinations of rows, i.e. row 1 is added to row 2, and row 1 multiplied by 2 is added to row 3. These linear combinations maintain the value of the determinant. The second equality comes from expansion along the first column

Review of main linear algebra problems

Compute the coordinates in a new basis, also known as solving a linear system $𝑨 𝒙 = 𝑰 𝒃$ when $𝑨 \in ℝ^{m \times m}$ square, non-singular
1. Compute $𝑳 𝑼$ factorization, $𝑳 𝑼 = 𝑨$
2. Solve $𝑳 𝒚 = 𝒃$ by forward substitution
3. Solve $𝑼 𝒙 = 𝒚$ by backward substition
Compute the cl
osest approximation to a high dimensional vector $𝒃 \in ℝ^{m}$ by linear combination of $n$ vectors $𝒂_{1}, \dots, 𝒂_{n} \in ℝ^{m}$ , $𝑨 = (\begin{array}{lll} 𝒂_{1} & \dots & 𝒂_{n} \end{array})$ , also known as the least squares problem
1. Compute $𝑸 𝑹$ factorization, $𝑸 𝑹 = 𝑨$ . The projector onto $C (𝑨) = C (𝑸)$ is $𝑷_{𝑸} = 𝑸 𝑸^{T}$
2. Projection of $𝒃$ onto $C (𝑨)$ is $𝑸 𝑸^{T} 𝒃$ . Set this equal to a linear combination of columns of $𝑨$ , $𝑨 𝒙 = 𝑸 𝑸^{T} 𝒃$ , Since $𝑨 = 𝑸 𝑹$ , solve the triangular system $𝑹 𝒙 = 𝑸^{T} 𝒃$ to find $𝒙$
For a square matrix $𝑨 \in ℂ^{m \times m}$ find those non-zero vectors whose directions are not changed by multiplication by $𝑨$ , $𝑨 𝒙 = λ 𝒙$ , known as the eigenvalue problem.

Characteristic polynomial of a matrix

Consider the eigenproblem $𝑨 𝒙 = λ 𝒙$ for $𝑨 \in ℂ^{m \times m}$ with $λ \in ℂ$ , and $𝒙 \in ℂ^{m}$ . Rewrite as
$𝑨 𝒙 = λ 𝒙 \Rightarrow (𝑨 - λ 𝑰) 𝒙 = 𝟎 .$
Since $𝒙 \neq 𝟎$ , a solution to eigenproblem exists only if $𝑨 - λ 𝑰$ is singular or $\det (𝑨 - λ 𝑰) = 0$
Investigate form of $\det (𝑨 - λ 𝑰) = 0$
$\det (𝑨 - λ 𝑰) = | \begin{array}{ccccc} a_{11} - λ & a & a_{13} & \dots & a_{1 m} \\ a_{21} & a_{22} - λ & a_{23} & \dots & a_{2 m} \\ a_{31} & a_{32} & a_{33} - λ & \dots & a_{3 m} \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ a_{m 1} & a_{m 2} & a_{m 3} & \dots & a_{m m} - λ \end{array} |$
Recall algebraic definition of a determinant as sum of products of index permutations to deduce that $\det (𝑨 - λ 𝑰) = 0$ is an $m^{th}$ degree polynomial in $λ$ , defined as the characteristic polynomial of $𝑨 \in ℂ^{m \times m}$
$p_{m} (λ) = \det (𝑨 - λ 𝑰)$