MAT223 Proofs

A set of vectors {v₁, v₂, ..., vₙ} in Rᵐ is linearly dependent if and only if the vector equation

x₁v₁ + x₂v₂ + ... + xₙvₙ = 0

has a “nontrivial” solution; that is, a solution other than

(x₁, x₂, ..., xₙ) = (0, 0, ..., 0).

Proof. Suppose that the set {v₁, v₂, ..., vₙ} is linearly dependent.

By relabeling, we may assume that v₁ ∈ Span(v₂, ..., vₙ). So, there are real numbers c₂, ..., cₙ so that v₁ = c₂v₂ + ... + cₙvₙ. Subtracting both sides by v₁ gives -v₁ + c₂v₂ + ... + cₙvₙ = 0. Hence, the vector equation x₁v₁ + x₂v₂ + ... + xₙvₙ = 0 has (x₁, ..., xₙ) = (-1, c₂, ..., cₙ) as a solution. Since x₁ = -1 ≠ 0, this solution is nontrivial, as needed.

Conversely, suppose that the vector equation x₁v₁ + x₂v₂ + ... + xₙvₙ = 0 has a nontrivial solution (c₁, c₂, ..., cₙ). Then, one of the cᵢ is nonzero. By relabeling, we may assume that c₁ ≠ 0. This gives c₁v₁ = -c₂v₂ - ... - cₙvₙ and so dividing on both sides by c₁ (which we can do since we know c₁ is nonzero) gives v₁ = -(c₂/c₁)v₂ - ... - (cₙ/c₁)vₙ ∈ Span(v₂, ..., vₙ). Hence, v₁ ∈ Span(v₂, ..., vₙ), and so the set {v₁, v₂, ..., vₙ} is linearly dependent. □

A set of vectors {v₁, v₂, ..., vₙ} in Rᵐ is linearly independent if and only if the reduced row echelon form of the matrix (v₁ v₂ ... vₙ) has a pivot in every column.

Proof. Suppose that the set {v₁, v₂, ..., vₙ} is linearly independent.

Then, the vector equation x₁v₁ + x₂v₂ + ... + xₙvₙ = 0 only has the trivial solution. This equation has the same solution set as the system of linear equations with augmented matrix (v₁ v₂ ... vₙ | 0). Since this equation has the trivial solution (x₁, x₂, ..., xₙ) = (0, 0, ..., 0), it is consistent. Hence, by Rouché-Capelli, the reduced row echelon form of the matrix (v₁ v₂ ... vₙ) must have a pivot in every column, as needed.

Conversely, suppose that the reduced row echelon form of the matrix (v₁ v₂ ... vₙ) has a pivot in every column. Then, by Rouché-Capelli, the system of linear equations with augmented matrix (v₁ v₂ ... vₙ | 0) only has one solution. Since (0, 0, ..., 0) is always a solution to this equation, it must be the only solution. So, the vector equation x₁v₁ + x₂v₂ + ... + xₙvₙ = 0 only has the trivial solution. Therefore, the set {v₁, ..., vₙ} is linearly independent. □

The span of any set of vectors in Rⁿ is a vector subspace of Rⁿ.

Proof. Suppose that V = Span(v₁, v₂, ..., vₘ) for vectors v₁, v₂, ..., vₘ in Rⁿ.

Observe that 0 ∈ V since we can write 0 = 0v₁ + ... + 0vₘ, and so V is not empty. Next, take any v, w in V.

Then we can write v = a₁v₁ + ... + aₘvₘ w = b₁v₁ + ... + bₘvₘ for scalars aᵢ, bᵢ ∈ R and so v + w = (a₁ + b₁)v₁ + ... + (aₘ + bₘ)vₘ ∈ Span(v₁, ..., vₘ). Hence, v + w ∈ V and so V is closed under vector addition.

Finally, for any scalar c ∈ R we have cv = (ca₁)v₁ + ... + (caₘ)vₘ ∈ Span(v₁, ..., vₘ). Hence, cv ∈ V and so V is closed under scalar multiplication.

Therefore, V is a vector space. To see that V is a subset of Rⁿ, note that each vᵢ ∈ Rⁿ and since Rⁿ is closed under scalar multiplication we know that cᵢvᵢ ∈ Rⁿ for all i = 1, ..., m. Hence, v = c₁v₁ + ... + cₘvₘ ∈ Rⁿ for all v ∈ V and so V ⊆ Rⁿ. □

Let A be an m × n matrix of the form A = (v₁ v₂ ... vₙ) where the vᵢ are vectors in Rᵐ. If the nth column of rref(A) does not have a pivot, then the vector vₙ is in Span(v₁, v₂, ..., vₙ₋₁).

Proof. Consider the vector equation x₁v₁ + x₂v₂ + ... + xₙ₋₁vₙ₋₁ = vₙ.

Since there is no pivot in the nth column of rref(A), then by Rouché-Capelli we know this system is consistent. That is, there exists (at least one) real number solution (c₁, ..., cₙ₋₁) to the equation above, which gives vₙ = c₁v₁ + ... + cₙ₋₁vₙ₋₁ ∈ Span(v₁, ..., vₙ₋₁), as needed. □

A linear transformation F is injective if and only if every column of rref(M_F) has a pivot.

Proof. Let M = M_F be the defining matrix of a linear transformation F : Rⁿ → Rᵐ.

By definition of the defining matrix, for any y ∈ Rᵐ, the set of vectors x ∈ Rⁿ satisfying F(x) = y is precisely the set of vectors satisfying the matrix-vector equation Mx = y. Observe that the matrix-vector equation Mx = y has the same solution set as the system of linear equations with augmented matrix (M | y). By Rouché-Capelli, rref(M | y) has a pivot in the last column if and only if the system has no solutions. Otherwise, the system has exactly one solution if and only if rref(M) has a pivot in every column. Therefore, the system has at most one solution if and only if rref(M) has a pivot in every column, as needed. □

Let F : Rⁿ → Rᵐ be a linear transformation with defining matrix M_F. Then, ker(F) = Nul(M_F) and im(F) = Col(M_F).

Proof. Let F have defining matrix M = M_F.

Then, ker(F) = {x ∈ Rⁿ : F(x) = 0}, by definition of ker(F) = {x ∈ Rⁿ : Mx = 0}, since M is the defining matrix of F = Nul(M), by definition of Nul(M).

Next, suppose that M has column vectors M = (v₁ ... vₙ). Then, im(F) = {F(x) : x ∈ Rⁿ}, by definition of im(F) = {Mx : x₁, ..., xₙ ∈ R}, since M is the defining matrix of F = {(v₁ ... vₙ)x : x₁, ..., xₙ ∈ R}, since M = (v₁ ... vₙ) = {x₁v₁ + ... + xₙvₙ : x₁, ..., xₙ ∈ R}, by definition of the matrix-vector product = Span(v₁, ..., vₙ), by definition of span = Col(M), by definition of the column space. □

The vector representation for the solution set to a consistent system of linear equations in n variables with coefficient matrix C is equal to p + Nul(C) := {p + v | v ∈ Nul(C)} where p is any particular vector solution to the system of linear equations.

Proof. Suppose that our system of linear equations has coefficient matrix C and particular solution p.

Then, the system has the same solution set as the matrix-vector equation Cx = b for a vector b ∈ Rⁿ. Let s be any solution to this matrix-vector equation. Since s and p are solutions to the matrix-vector equation Cx = b we have Cs = b and Cp = b. So, C(s - p) = Cs - Cp = 0, and hence s - p ∈ Nul(C). That is, s - p = v for some v ∈ Nul(C) and so adding p to both sides gives s = p + v ∈ p + Nul(C).

Conversely, take any p + v ∈ p + Nul(C). Since p is a solution to Cx = b we have Cp = b. Furthermore, since v ∈ Nul(C) we have Cv = 0. So, C(p + v) = Cp + Cv = b + 0 = b, and so p + v is a solution to Cx = b, as needed. □

For an n × n matrix A, the set of eigenvectors of A corresponding to an eigenvalue λ is equal to the nonzero vectors in Nul(A - λIₙ).

Proof.

Observe v ∈ Nul(A - λIₙ) if and only if (A - λIₙ)v = 0 ⟺ Av - λv = 0 ⟺ Av = λv, as needed.

A real number λ is an eigenvalue of A if and only if det(A - λIₙ) = 0.

Proof. Consider the vector equation (A - λIₙ)x = 0.

By definition, v is an eigenvector of A with eigenvalue λ precisely when Av = λv, which can be rewritten as (A - λIₙ)v = 0. Since eigenvalues are nonzero, we know that λ is an eigenvalue of A if and only if there is a nonzero solution v to the equation above. Since 0 is also a solution to the equation, λ is an eigenvalue of A if and only if the equation has infinitely many solutions. By Rouché-Capelli, this takes places precisely when rref(A - λIₙ) has a column without a pivot, which is equivalent to the matrix A - λIₙ not being invertible. Thus, the result follows since the determinant is zero if and only if matrix is not invertible. □

Let V be a vector space with basis C = {c₁, ..., cₙ}. Then, a subset B = {b₁, ..., bₙ} of V is a basis for V if and only if the matrix ([b₁]_C ... [bₙ]_C) is invertible. In this case, we have M_C←B = ([b₁]_C ... [bₙ]_C). and furthermore (M_C←B)⁻¹ = M_B←C.

Proof. Suppose first that B is a basis.

Then, for any x in V, let [x]_B be the vector with entries x₁, ..., xₙ. Then we have x = x₁b₁ + ... + xₙbₙ. Writing this equation in C-coordinates gives [x]_C = [x₁b₁ + ... + xₙbₙ]_C. This gives [x]_C = x₁[b₁]_C + ... + xₙ[bₙ]_C = ([b₁]C ... [bₙ]C) [x]_B = ([b₁]_C ... [bₙ]_C) [x]_B, and so M_C←B = ([b₁]_C ... [bₙ]_C). We know that the columns of M_C←B are linearly independent, and so by the Invertible Matrix Theorem M_C←B is invertible. So, [x]_C = M_C←B[x]_B implies [x]_B = (M_C←B)⁻¹[x]_C. Hence, we have (M_C←B)⁻¹ = M_B←C.

Conversely, suppose that the matrix ([b₁]_C ... [bₙ]_C) is invertible. To see that B is linearly independent, consider the vector equation α₁b₁ + ... + αₙbₙ = 0. Writing this equation in C-coordinates gives α₁[b₁]_C + ... + αₙ[bₙ]_C = 0. Since ([b₁]_C ... [bₙ]_C) is invertible, its columns must be linearly independent, and so α₁ = ... = αₙ = 0, as needed. Finally, if B did not span V, then we would have a basis for V of dimension larger than n. This contradicts the fact that V is n-dimensional, and so B is a basis as needed. □

Let F : Rⁿ → Rⁿ be a linear transformation and B be any basis for Rⁿ. Then, there exists a unique n × n matrix M so that [F(x)]_B = M[x]_B. Furthermore, we have M = ([F(b₁)]_B ... [F(bₙ)]_B).

Proof. Take any x ∈ Rⁿ and write x = x₁b₁ + ... + xₙbₙ.

Then, [F(x)]_B = [F(x₁b₁ + ... + xₙbₙ)]_B = [x₁F(b₁) + ... + xₙF(bₙ)]_B since F is linear

= x₁[F(b₁)]_B + ... + xₙ[F(bₙ)]_B = ([F(b₁)]_B ... [F(bₙ)]_B) (x₁, ..., xₙ)ᵀ

= ([F(b₁)]_B ... [F(bₙ)]_B) [x]_B, as needed.

Two n × n matrices B and C are similar if and only if there exists an invertible n × n matrix P so that B = P⁻¹CP.

Proof. Suppose that B and C are similar n × n matrices. Then, by definition, there exists a linear transformation F : Rⁿ → Rⁿ and bases ℬ, 𝒞 for Rⁿ so that M_F,ℬ = B and M_F,𝒞 = C. Recalling our definition of defining matrices from the previous section, we have [F(x)]_𝒞 = C[x]_𝒞. Now, let's use our change of basis matrix: we have M_𝒞←ℬ[F(x)]_ℬ = [F(x)]𝒞 and M_𝒞←ℬ[x]_ℬ = [x]_𝒞. Replacing this into the equation above yields M_𝒞←ℬ[F(x)]_ℬ = C M_𝒞←ℬ[x]_ℬ. Setting P := M_𝒞←ℬ we have P[F(x)]_ℬ = CP[x]_ℬ. Recall that P is invertible, and so we can multiply the left-hand side of the equality above to get [F(x)]_ℬ = P⁻¹CP[x]_ℬ. But then, by definition of defining matrices, B = P⁻¹CP.

Conversely, suppose that B = P⁻¹CP for an invertible matrix P. Let F : Rⁿ → Rⁿ be the linear transformation with standard defining matrix M_F,ℰ = C. Let ℬ = {b₁, ..., bₙ} be the set of vectors so that P = ([b₁]_ℰ ... [bₙ]_ℰ). Since P is invertible, we have that ℬ is a basis for Rⁿ with P = M_ℰ←ℬ and P⁻¹ = M_ℬ←ℰ. So, B[x]_ℬ = P⁻¹CP[x]_ℬ = M_ℬ←ℰ C M_ℰ←ℬ[x]_ℬ = M_ℬ←ℰ C [x]_ℰ = M_ℬ←ℰ [F(x)]_ℰ = [F(x)]_ℬ. Hence, B = M_F,ℬ is the defining matrix of F with respect to the basis ℬ. So, we've found a single linear transformation F : Rⁿ → Rⁿ so that C = M_F,ℰ and B = M_F,ℬ. Therefore, B and C are similar. □

Let ℬ be an orthonormal basis for Rⁿ and take any vectors x, y in Rⁿ. Then [x]_ℬ · [y]_ℬ = x · y. In particular, we have ||x|| = ||[x]_ℬ||.

Proof. Suppose that ℬ = {v₁, v₂, ..., vₙ} is an orthonormal basis for Rⁿ and write [x]_ℬ = (x₁, ..., xₙ) and [y]_ℬ = (y₁, ..., yₙ).

That is, x = x₁v₁ + ... + xₙvₙ y = y₁v₁ + ... + yₙvₙ. Then we have x · y = (x₁v₁ + ... + xₙvₙ) · (y₁v₁ + ... + yₙvₙ) Using the distributive properties of the dot product, we'll end up with a sum of terms of the form xᵢyⱼvᵢ · vⱼ. But, since we know that vᵢ · vⱼ = 0 whenever i ≠ j then we have x · y = x₁y₁v₁ · v₁ + ... xₙyₙvₙ · vₙ. But we also know that vᵢ · vᵢ = ||v||² = 1, since our basis is orthonormal. So, we have x · y = x₁y₁ + ... + xₙyₙ as desired. □

If an n × n matrix Q is orthogonal, then it preserves dot products and norms. That is, for any vectors u, v in Rⁿ:

1. Qu · Qv = u · v

2. ||Qu|| = ||u||

3. u · v = 0 ⟺ Qu · Qv = 0 (Preserves orthogonality)

Proof. Suppose that Q is orthogonal.

Observe first that Q⁻¹ is also orthogonal. Therefore Q⁻¹ = Qᵀ and so QᵀQ = I_n. This gives (Qᵀ)⁻¹ = Q ⇒ (Qᵀ)⁻¹ = (Qᵀ)ᵀ and so Q⁻¹ = Qᵀ is orthogonal.

Next, let Q⁻¹ = (b₁ ... bₙ), and observe that Q⁻¹ is the change of basis matrix Q⁻¹ = M_ℰ←ℬ where ℬ = {b₁, ..., bₙ}. So, we have Q = M_ℬ←ℰ and since ℬ is an orthonormal basis, then we have Qu · Qv = [u]_ℬ · [v]_ℬ = u · v, as needed. Thus, we have ||Qu|| = u · u = ||u||, and since Qu · Qv = u · v then we have u · v = 0 ⟺ Qu · Qv = 0. □

Let A be an m × n matrix. Then, there exists an orthonormal basis for Rⁿ of eigenvectors of AᵀA so that {Av₁, ..., Avₙ} is an orthogonal subset of Rᵐ. Furthermore, if we reindex our basis so that Av₁, ..., Av_r are nonzero, and Av_r+1 = ... = Avₙ = 0, then {Av₁, ..., Av_r} forms an orthogonal basis for Col(A).

Proof. Observe first that AᵀA is symmetric.

Then (AᵀA)ᵀ = Aᵀ(Aᵀ)ᵀ = AᵀA. So, by the Spectral Theorem, there exists an orthonormal basis for Rⁿ of eigenvectors of AᵀA. Suppose that the eigenvectors vᵢ of AᵀA have corresponding eigenvalues λᵢ. Then, for any i ≠ j we have (Avᵢ) · (Avⱼ) = (Avᵢ)ᵀ (Avⱼ) = vᵢᵀ Aᵀ A vⱼ = vᵢᵀ (λⱼvⱼ) = vᵢ · (λⱼvⱼ) = λⱼ(vᵢ · vⱼ) = 0, where the final equality follows because vᵢ and vⱼ are orthogonal when i ≠ j. Hence, {Av₁, ..., Avₘ} is an orthogonal subset of Rᵐ.

Next, if we reindex as in the theorem statement, we see that Ay ∈ Col(A) if and only if Ay = A(x₁v₁ + ... + xₙvₙ) = x₁Av₁ + ... + x_rAv_r + 0, and so Col(A) = Span(Av₁, ..., Av_r). Since {Av₁, ..., Av_r} is orthogonal, then this set is linearly independent, and hence is a basis as needed. □

Let A be an m × n matrix and λ₁, ..., λₙ be the eigenvalues of AᵀA. Then, λᵢ ≥ 0 and the singular values of A are given by σᵢ = √λᵢ.

Proof. We have σᵢ² = ||Avᵢ||² = (Avᵢ) · (Avᵢ) = (Avᵢ)ᵀ (Avᵢ) = vᵢᵀ Aᵀ Avᵢ = vᵢᵀ λᵢvᵢ = λᵢvᵢ · vᵢ = λᵢ||vᵢ||² = λᵢ, where the final equality follows because the vᵢ form an orthonormal set. Hence, σᵢ² = λᵢ and so λᵢ ≥ 0 and σᵢ = √λᵢ. □