27 Proof Techniques for Linear Algebra

This appendix is a guide to common proof techniques in linear algebra.

It is not meant to replace the main chapters. Instead, it gives reusable proof patterns that appear throughout the book. Linear algebra proofs often look difficult at first because the objects are abstract: vectors, matrices, subspaces, transformations, bases, and dimensions. But many proofs follow a small number of templates.

The goal of this appendix is to help you recognize those templates.

27.1 1. What is a proof?

A proof is a clear explanation that shows why a statement must be true.

In linear algebra, a proof often does one of the following:

verifies that an object satisfies a definition,
shows that two sets are equal,
proves that a system has or does not have solutions,
proves that a transformation preserves structure,
proves that a formula has the required property,
uses dimension or rank to count degrees of freedom,
uses orthogonality or projection to show best approximation,
uses eigenvectors or singular vectors to reveal matrix structure.

A good proof is not only correct. It should also explain the main idea.

Proof mindset

When reading or writing a proof, ask:

What is being assumed?
What must be shown?
Which definition is relevant?
What algebraic or geometric structure should be used?
What is the shortest clear path from the assumptions to the conclusion?

27.2 2. Start with definitions

Many linear algebra proofs begin by unpacking a definition.

For example:

To prove a set is a subspace, use the subspace definition.
To prove vectors are linearly independent, use the definition of linear independence.
To prove a map is linear, use the definition of linearity.
To prove \(A\) is invertible, use the definition of inverse or an equivalent theorem.
To prove \(v\) is an eigenvector, verify \(Av=\lambda v\) for some scalar \(\lambda\).
To prove \(P\) is a projection matrix, check \(P^2=P\).
To prove \(Q\) is orthogonal, check \(Q^TQ=I\).

Definition-first principle

Before trying a clever idea, write down the definition of the object or property you need to prove.

27.3 3. Direct proof

A direct proof starts from the assumptions and logically derives the conclusion.

27.3.1 Template

To prove:

\[ P \Longrightarrow Q, \]

start by assuming \(P\) is true, then show that \(Q\) follows.

27.3.2 Example: linear combinations of vectors in a subspace stay in the subspace

Claim. If \(W\) is a subspace of \(\mathbb{R}^n\) and \(u,v\in W\), then for any scalars \(a,b\),

\[ au+bv\in W. \]

Proof. Since \(W\) is a subspace, it is closed under scalar multiplication. Therefore

\[ au\in W \]

and

\[ bv\in W. \]

Since \(W\) is also closed under addition,

\[ au+bv\in W. \]

This proves the claim.

27.3.3 What happened?

We used the definition of subspace directly.

27.4 4. Proving a set is a subspace

A subset \(W\subseteq\mathbb{R}^n\) is a subspace if:

\(0\in W\),
if \(u,v\in W\), then \(u+v\in W\),
if \(u\in W\) and \(c\in\mathbb{R}\), then \(cu\in W\).

Equivalently, it is enough to show:

\(0\in W\),
if \(u,v\in W\) and \(a,b\in\mathbb{R}\), then \(au+bv\in W\).

27.4.1 Template

To prove \(W\) is a subspace:

Take arbitrary \(u,v\in W\).
Take arbitrary scalars \(a,b\).
Show \(au+bv\in W\).
Check that \(0\in W\) if it is not automatic.

27.4.2 Example: null space is a subspace

Claim. For any \(m\times n\) matrix \(A\),

\[ \operatorname{Null}(A)=\{x\in\mathbb{R}^n:Ax=0\} \]

is a subspace of \(\mathbb{R}^n\).

Proof. First,

\[ A0=0, \]

\[ 0\in\operatorname{Null}(A). \]

Now let \(u,v\in\operatorname{Null}(A)\) and let \(a,b\in\mathbb{R}\).

Then

\[ Au=0 \]

and

\[ Av=0. \]

Using linearity of matrix multiplication,

\[ A(au+bv)=aAu+bAv. \]

Since \(Au=0\) and \(Av=0\),

\[ A(au+bv)=a0+b0=0. \]

Thus

\[ au+bv\in\operatorname{Null}(A). \]

Therefore \(\operatorname{Null}(A)\) is a subspace.

27.4.3 Common mistake

Do not prove only that \(u+v\in W\) and forget scalar multiplication. A subspace must be closed under both operations.

27.5 5. Proving a set is not a subspace

To prove that a set is not a subspace, it is enough to show that one subspace condition fails.

Common strategies:

show \(0\notin W\),
find \(u,v\in W\) such that \(u+v\notin W\),
find \(u\in W\) and scalar \(c\) such that \(cu\notin W\).

27.5.1 Example

Let

\[ W=\left\{ \begin{bmatrix} x\\ y \end{bmatrix} \in\mathbb{R}^2:x+y=1 \right\}. \]

Then

\[ 0= \begin{bmatrix} 0\\ 0 \end{bmatrix} \]

does not satisfy \(x+y=1\).

Therefore

\[ 0\notin W. \]

So \(W\) is not a subspace.

27.5.2 Key idea

A nonhomogeneous linear equation usually gives an affine set, not a subspace.

27.6 6. Proving span statements

To prove that a vector \(b\) lies in a span,

\[ b\in\operatorname{span}\{v_1,\ldots,v_k\}, \]

you must show that there exist scalars \(c_1,\ldots,c_k\) such that

\[ b=c_1v_1+\cdots+c_kv_k. \]

27.6.1 Template

Write the desired equation:

\[ b=c_1v_1+\cdots+c_kv_k. \]

Convert it into a linear system.
Solve for the coefficients.
If a solution exists, \(b\) is in the span.
If no solution exists, \(b\) is not in the span.

27.6.2 Example

Let

\[ v_1= \begin{bmatrix} 1\\ 2 \end{bmatrix}, \qquad v_2= \begin{bmatrix} 3\\ 1 \end{bmatrix}, \qquad b= \begin{bmatrix} 4\\ 3 \end{bmatrix}. \]

We ask whether

\[ b=c_1v_1+c_2v_2. \]

This gives

\[ c_1 \begin{bmatrix} 1\\ 2 \end{bmatrix} + c_2 \begin{bmatrix} 3\\ 1 \end{bmatrix} = \begin{bmatrix} 4\\ 3 \end{bmatrix}. \]

Equivalently,

\[ \begin{cases} c_1+3c_2=4,\\ 2c_1+c_2=3. \end{cases} \]

Solving gives

\[ c_1=1, \qquad c_2=1. \]

Therefore

\[ b=v_1+v_2, \]

\[ b\in\operatorname{span}\{v_1,v_2\}. \]

27.7 7. Proving linear independence

Vectors \(v_1,\ldots,v_k\) are linearly independent if

\[ c_1v_1+\cdots+c_kv_k=0 \]

implies

\[ c_1=\cdots=c_k=0. \]

27.7.1 Template

To prove \(v_1,\ldots,v_k\) are linearly independent:

Start with

\[ c_1v_1+\cdots+c_kv_k=0. \]

Show that the only possible solution is

\[ c_1=\cdots=c_k=0. \]

27.7.2 Example

Let

\[ v_1= \begin{bmatrix} 1\\ 0 \end{bmatrix}, \qquad v_2= \begin{bmatrix} 1\\ 1 \end{bmatrix}. \]

Suppose

\[ c_1v_1+c_2v_2=0. \]

Then

\[ c_1 \begin{bmatrix} 1\\ 0 \end{bmatrix} + c_2 \begin{bmatrix} 1\\ 1 \end{bmatrix} = \begin{bmatrix} 0\\ 0 \end{bmatrix}. \]

\[ \begin{bmatrix} c_1+c_2\\ c_2 \end{bmatrix} = \begin{bmatrix} 0\\ 0 \end{bmatrix}. \]

Thus

\[ c_2=0 \]

and then

\[ c_1=0. \]

Therefore the vectors are linearly independent.

27.8 8. Proving linear dependence

Vectors are linearly dependent if there exists a nontrivial relation

\[ c_1v_1+\cdots+c_kv_k=0, \]

where not all \(c_i\) are zero.

27.8.1 Template

To prove dependence, find one nontrivial linear relation.

27.8.2 Example

Let

\[ v_1= \begin{bmatrix} 1\\ 2 \end{bmatrix}, \qquad v_2= \begin{bmatrix} 2\\ 4 \end{bmatrix}. \]

Since

\[ v_2=2v_1, \]

we have

\[ 2v_1-v_2=0. \]

The coefficients \(2\) and \(-1\) are not both zero.

Therefore \(v_1\) and \(v_2\) are linearly dependent.

27.9 9. Proving a set is a basis

A set \(\{v_1,\ldots,v_k\}\) is a basis for \(W\) if:

it spans \(W\),
it is linearly independent.

27.9.1 Template

To prove a set is a basis:

Show every vector in \(W\) can be written as a linear combination of the given vectors.
Show the given vectors are linearly independent.

27.9.2 Shortcut in finite dimensions

If \(W\) has dimension \(k\) and you have \(k\) vectors in \(W\), then either of the following is enough:

if the \(k\) vectors are linearly independent, they form a basis;
if the \(k\) vectors span \(W\), they form a basis.

27.9.3 Example

To prove two vectors form a basis of \(\mathbb{R}^2\), it is enough to show that they are linearly independent.

Equivalently, if they are columns of a \(2\times 2\) matrix \(A\), show

\[ \det(A)\ne 0. \]

27.10 10. Proving uniqueness

Many linear algebra results contain uniqueness statements.

Examples:

coordinates in a basis are unique,
the inverse of a matrix is unique,
projection onto a subspace is unique,
least-squares fitted vector is unique,
solution to \(Ax=b\) is unique when \(A\) is invertible.

27.10.1 Template

To prove uniqueness:

Suppose there are two objects satisfying the required property.
Show they must be equal.

27.10.2 Example: uniqueness of coordinates

Claim. If \(B=\{b_1,\ldots,b_n\}\) is a basis and

\[ x=c_1b_1+\cdots+c_nb_n \]

and

\[ x=d_1b_1+\cdots+d_nb_n, \]

then

\[ c_i=d_i \]

for all \(i\).

Proof. Subtract the two expressions:

\[ 0=(c_1-d_1)b_1+\cdots+(c_n-d_n)b_n. \]

Since \(B\) is linearly independent, all coefficients must be zero:

\[ c_i-d_i=0. \]

Therefore

\[ c_i=d_i \]

for every \(i\).

This proves uniqueness.

27.11 11. Proving set equality

To prove two sets are equal,

\[ S=T, \]

show both inclusions:

\[ S\subseteq T \]

and

\[ T\subseteq S. \]

27.11.1 Template

Let \(x\in S\). Prove \(x\in T\).
Let \(x\in T\). Prove \(x\in S\).
Conclude \(S=T\).

27.11.2 Example: row space and null space are orthogonal complements

One important result is

\[ \operatorname{Row}(A)^\perp=\operatorname{Null}(A). \]

A full proof can be organized by two inclusions.

27.11.3 First inclusion

Let

\[ x\in\operatorname{Null}(A). \]

Then

\[ Ax=0. \]

Each entry of \(Ax\) is the dot product of one row of \(A\) with \(x\).

Thus \(x\) is orthogonal to every row of \(A\), and therefore to every linear combination of rows.

\[ x\in\operatorname{Row}(A)^\perp. \]

Therefore

\[ \operatorname{Null}(A)\subseteq\operatorname{Row}(A)^\perp. \]

27.11.4 Second inclusion

Let

\[ x\in\operatorname{Row}(A)^\perp. \]

Then \(x\) is orthogonal to every row of \(A\).

Therefore every row dot product with \(x\) is zero.

That means

\[ Ax=0. \]

\[ x\in\operatorname{Null}(A). \]

Therefore

\[ \operatorname{Row}(A)^\perp\subseteq\operatorname{Null}(A). \]

Together,

\[ \operatorname{Row}(A)^\perp=\operatorname{Null}(A). \]

27.12 12. If and only if proofs

An “if and only if” statement has two directions.

To prove

\[ P\Longleftrightarrow Q, \]

prove:

\(P\Longrightarrow Q\),
\(Q\Longrightarrow P\).

27.12.1 Example: invertibility and trivial null space

Claim. An \(n\times n\) matrix \(A\) is invertible if and only if

\[ \operatorname{Null}(A)=\{0\}. \]

A full proof may use the Invertible Matrix Theorem. But the structure is still two directions.

27.12.2 Direction 1

Assume \(A\) is invertible.

\[ Ax=0, \]

multiply both sides by \(A^{-1}\):

\[ A^{-1}Ax=A^{-1}0. \]

Thus

\[ x=0. \]

\[ \operatorname{Null}(A)=\{0\}. \]

27.12.3 Direction 2

Assume

\[ \operatorname{Null}(A)=\{0\}. \]

Then the columns of \(A\) are linearly independent. Since there are \(n\) columns in \(\mathbb{R}^n\), they form a basis of \(\mathbb{R}^n\).

Therefore \(A\) has a pivot in every column and every row, so \(A\) is invertible.

27.13 13. Proof by contradiction

In proof by contradiction, assume the opposite of what you want to prove, and derive an impossibility.

27.13.1 Template

To prove \(P\):

Assume \(P\) is false.
Use the assumptions to derive a contradiction.
Conclude \(P\) must be true.

27.13.2 Example: eigenvectors for distinct eigenvalues are independent

We prove the case of two eigenvectors.

Claim. If \(v_1\) and \(v_2\) are eigenvectors of \(A\) with distinct eigenvalues \(\lambda_1\) and \(\lambda_2\), then \(v_1,v_2\) are linearly independent.

Proof. Suppose, for contradiction, that \(v_1,v_2\) are linearly dependent.

Since \(v_1\) is nonzero, this means

\[ v_2=cv_1 \]

for some scalar \(c\ne 0\).

Apply \(A\):

\[ Av_2=A(cv_1)=cAv_1=c\lambda_1v_1. \]

But \(v_2\) is an eigenvector with eigenvalue \(\lambda_2\), so

\[ Av_2=\lambda_2v_2=\lambda_2cv_1. \]

Thus

\[ c\lambda_1v_1=c\lambda_2v_1. \]

Since \(c\ne 0\) and \(v_1\ne 0\),

\[ \lambda_1=\lambda_2. \]

This contradicts the assumption that the eigenvalues are distinct.

Therefore \(v_1\) and \(v_2\) are linearly independent.

27.14 14. Proof by contraposition

To prove

\[ P\Longrightarrow Q, \]

you may prove the contrapositive:

\[ \text{not }Q \Longrightarrow \text{not }P. \]

This is logically equivalent.

27.14.1 Example

Statement:

If the columns of \(A\) are linearly independent, then \(Ax=0\) has only the trivial solution.

Contrapositive:

If \(Ax=0\) has a nontrivial solution, then the columns of \(A\) are linearly dependent.

This is often easier.

If \(Ax=0\) has a nontrivial solution, then for some coefficients not all zero,

\[ x_1a_1+\cdots+x_na_n=0. \]

This is a nontrivial linear relation among the columns. Therefore the columns are dependent.

27.15 15. Induction proofs

Induction is useful for statements involving powers, dimensions, recurrences, or repeated matrix multiplication.

27.15.1 Template

To prove a statement \(P(k)\) for all integers \(k\ge 0\):

Prove the base case \(P(0)\).
Assume \(P(k)\) is true.
Prove \(P(k+1)\).
Conclude by induction.

27.15.2 Example: powers on eigenvectors

Claim. If

\[ Av=\lambda v, \]

then

\[ A^kv=\lambda^kv \]

for every integer \(k\ge 0\).

Proof. For \(k=0\),

\[ A^0v=Iv=v \]

and

\[ \lambda^0v=v. \]

So the statement is true for \(k=0\).

Assume

\[ A^kv=\lambda^kv. \]

Then

\[ A^{k+1}v=A(A^kv). \]

Using the induction hypothesis,

\[ A^{k+1}v=A(\lambda^kv). \]

Since \(\lambda^k\) is a scalar,

\[ A^{k+1}v=\lambda^kAv. \]

Since \(Av=\lambda v\),

\[ A^{k+1}v=\lambda^k\lambda v=\lambda^{k+1}v. \]

Thus the result holds for \(k+1\).

By induction,

\[ A^kv=\lambda^kv \]

for all \(k\ge 0\).

27.16 16. Dimension arguments

Dimension arguments prove results by counting the number of independent directions.

Common facts:

A subspace of dimension \(k\) cannot contain more than \(k\) linearly independent vectors.
A set of \(k\) independent vectors in a \(k\)-dimensional space is a basis.
A set of \(k\) spanning vectors in a \(k\)-dimensional space is a basis.
If \(U\subseteq W\) and \(\dim(U)=\dim(W)\), then \(U=W\).

27.16.1 Example

Claim. If \(U\subseteq W\) and \(\dim(U)=\dim(W)\), then \(U=W\).

Proof. Let

\[ \dim(U)=\dim(W)=k. \]

Take a basis of \(U\):

\[ u_1,\ldots,u_k. \]

Since \(U\subseteq W\), these vectors are also in \(W\).

They are linearly independent in \(U\), so they are also linearly independent in \(W\).

Since \(W\) has dimension \(k\), these \(k\) independent vectors form a basis of \(W\).

Thus they span \(W\).

But they also span \(U\).

Therefore \(U=W\).

27.17 17. Rank-nullity proofs

Rank-nullity is one of the most useful counting tools:

\[ \operatorname{rank}(A)+\dim\operatorname{Null}(A)=n \]

for an \(m\times n\) matrix \(A\).

27.17.1 How to use it

If you know rank, you know nullity:

\[ \dim\operatorname{Null}(A)=n-\operatorname{rank}(A). \]

If you know nullity, you know rank:

\[ \operatorname{rank}(A)=n-\dim\operatorname{Null}(A). \]

27.17.2 Example

If \(A\) is a \(5\times 8\) matrix and

\[ \operatorname{rank}(A)=3, \]

then

\[ \dim\operatorname{Null}(A)=8-3=5. \]

27.18 18. Proving formulas by checking defining properties

Sometimes the easiest way to prove a formula is correct is to show that it has the required defining property.

27.18.1 Example: inverse formula

To prove a matrix \(B\) is the inverse of \(A\), check

\[ AB=I \]

and

\[ BA=I. \]

27.18.2 Example: projection formula

To prove

\[ p=\frac{a\cdot b}{a\cdot a}a \]

is the projection of \(b\) onto \(\operatorname{span}\{a\}\), check:

\(p\in\operatorname{span}\{a\}\),
\(b-p\perp a\).

Indeed,

\[ p \]

is a scalar multiple of \(a\), so

\[ p\in\operatorname{span}\{a\}. \]

Now compute:

\[ (b-p)\cdot a = \left(b-\frac{a\cdot b}{a\cdot a}a\right)\cdot a. \]

Using dot product properties,

\[ (b-p)\cdot a = b\cdot a-\frac{a\cdot b}{a\cdot a}(a\cdot a). \]

Thus

\[ (b-p)\cdot a=b\cdot a-a\cdot b=0. \]

Therefore \(b-p\) is orthogonal to the line.

So \(p\) is the projection.

27.19 19. Proving linearity

To prove a map \(T\) is linear, show:

\[ T(x+y)=T(x)+T(y) \]

and

\[ T(cx)=cT(x). \]

Equivalently, show:

\[ T(ax+by)=aT(x)+bT(y) \]

for all vectors \(x,y\) and scalars \(a,b\).

27.19.1 Example: matrix transformations are linear

Let

\[ T(x)=Ax. \]

Then

\[ T(ax+by)=A(ax+by). \]

Using matrix multiplication rules,

\[ A(ax+by)=aAx+bAy. \]

Thus

\[ T(ax+by)=aT(x)+bT(y). \]

Therefore \(T\) is linear.

27.20 20. Proving a map is not linear

To prove a map is not linear, find one counterexample.

Common tests:

Does \(T(0)=0\)?
Does \(T(x+y)=T(x)+T(y)\) fail?
Does \(T(cx)=cT(x)\) fail?

27.20.1 Example

Let

\[ T(x)=Ax+b \]

with

\[ b\ne 0. \]

Then

\[ T(0)=b\ne 0. \]

Since every linear map must send \(0\) to \(0\), this map is not linear.

It is affine, not linear.

27.21 21. Orthogonality proofs

Orthogonality proofs usually use dot products.

27.21.1 Common patterns

To prove \(x\perp y\), show

\[ x\cdot y=0. \]

To prove \(x\perp W\), show

\[ x\cdot w=0 \]

for every \(w\in W\).

If \(W=\operatorname{span}\{w_1,\ldots,w_k\}\), it is enough to show

\[ x\cdot w_i=0 \]

for every basis or spanning vector \(w_i\).

27.21.2 Example

\[ A^Tr=0, \]

then \(r\) is orthogonal to every column of \(A\).

Why?

The entries of \(A^Tr\) are the dot products

\[ a_i\cdot r, \]

where \(a_i\) are the columns of \(A\).

If all entries are zero, then

\[ a_i\cdot r=0 \]

for every column.

Therefore \(r\) is orthogonal to \(\operatorname{Col}(A)\).

27.22 22. Projection and closest-point proofs

Projection proofs often use the Pythagorean theorem.

27.22.1 Key idea

Let \(W\) be a subspace and let

\[ p=\operatorname{proj}_W(b). \]

Then

\[ b=p+e, \]

where

\[ p\in W \]

and

\[ e\in W^\perp. \]

For any other vector \(w\in W\),

\[ b-w=e+(p-w). \]

Since

\[ e\perp(p-w), \]

we have

\[ \|b-w\|^2=\|e\|^2+\|p-w\|^2. \]

Thus

\[ \|b-w\|^2\ge \|e\|^2. \]

The minimum occurs when

\[ w=p. \]

Therefore \(p\) is the closest vector in \(W\) to \(b\).

27.23 23. Least-squares proofs

Least-squares proofs are projection proofs in matrix form.

The least-squares problem is

\[ \min_x \|b-Ax\|. \]

The fitted vector is

\[ A\hat x. \]

It must be the projection of \(b\) onto \(\operatorname{Col}(A)\).

Therefore the residual

\[ r=b-A\hat x \]

must satisfy

\[ r\perp \operatorname{Col}(A). \]

This is equivalent to

\[ A^Tr=0. \]

Thus

\[ A^T(b-A\hat x)=0. \]

Expanding gives

\[ A^TA\hat x=A^Tb. \]

This proves the normal equations.

27.24 24. Determinant proof patterns

Determinant proofs often use:

row operation effects,
triangular matrices,
multiplicativity,
volume interpretation,
invertibility test.

27.24.1 Common identities

\[ \det(AB)=\det(A)\det(B). \]

\[ \det(A^T)=\det(A). \]

If \(A\) is triangular,

\[ \det(A)=\prod_i a_{ii}. \]

If \(A\) is invertible,

\[ \det(A^{-1})=\frac{1}{\det(A)}. \]

27.24.2 Example

If \(A\) is orthogonal, then

\[ Q^TQ=I. \]

Taking determinants,

\[ \det(Q^TQ)=\det(I). \]

\[ \det(Q^T)\det(Q)=1. \]

Since

\[ \det(Q^T)=\det(Q), \]

we get

\[ (\det Q)^2=1. \]

Therefore

\[ \det(Q)=\pm 1. \]

27.25 25. Eigenvalue proof patterns

Eigenvalue proofs usually begin with

\[ Av=\lambda v. \]

27.25.1 To prove \(\lambda\) is an eigenvalue

Find a nonzero vector \(v\) such that

\[ Av=\lambda v. \]

27.25.2 To find eigenvalues

Use

\[ (A-\lambda I)v=0. \]

For a nonzero solution, the matrix \(A-\lambda I\) must be singular.

Thus

\[ \det(A-\lambda I)=0. \]

27.25.3 To prove an eigenspace is a subspace

Use

\[ E_\lambda=\operatorname{Null}(A-\lambda I). \]

Since null spaces are subspaces, eigenspaces are subspaces.

27.26 26. Symmetric matrix proof patterns

Symmetric matrices satisfy

\[ A^T=A. \]

This identity allows dot products to move \(A\) from one side to the other:

\[ (Ax)\cdot y=x\cdot(Ay). \]

27.26.1 Example: eigenvectors for distinct eigenvalues are orthogonal

Suppose \(A\) is symmetric,

\[ Av=\lambda v, \]

and

\[ Aw=\mu w, \]

with

\[ \lambda\ne\mu. \]

Then

\[ (Av)\cdot w=\lambda(v\cdot w). \]

Also, because \(A\) is symmetric,

\[ (Av)\cdot w=v\cdot(Aw). \]

Since \(Aw=\mu w\),

\[ v\cdot(Aw)=\mu(v\cdot w). \]

Therefore

\[ \lambda(v\cdot w)=\mu(v\cdot w). \]

\[ (\lambda-\mu)(v\cdot w)=0. \]

Since \(\lambda\ne\mu\),

\[ v\cdot w=0. \]

Thus

\[ v\perp w. \]

27.27 27. Quadratic form proof patterns

For symmetric \(A\), the quadratic form is

\[ q(x)=x^TAx. \]

Use the spectral theorem:

\[ A=QDQ^T. \]

Let

\[ y=Q^Tx. \]

Then

\[ x^TAx=y^TDy=\lambda_1y_1^2+\cdots+\lambda_ny_n^2. \]

This formula proves many results.

27.27.1 Positive definite criterion

If all \(\lambda_i>0\), then for \(x\ne 0\), we also have \(y\ne 0\) because \(Q\) is invertible.

Thus

\[ x^TAx=\lambda_1y_1^2+\cdots+\lambda_ny_n^2>0. \]

So \(A\) is positive definite.

If some eigenvalue \(\lambda_j<0\), then choose \(y=e_j\). Then

\[ y^TDy=\lambda_j<0. \]

So the quadratic form is not positive semidefinite.

27.28 28. SVD proof patterns

The SVD is built from the spectral theorem applied to

\[ A^TA. \]

Since

\[ A^TA \]

is symmetric positive semidefinite, it has orthonormal eigenvectors \(v_i\) and nonnegative eigenvalues \(\lambda_i\).

Define

\[ \sigma_i=\sqrt{\lambda_i}. \]

For \(\sigma_i>0\), define

\[ u_i=\frac{Av_i}{\sigma_i}. \]

Then

\[ Av_i=\sigma_i u_i. \]

This is the singular vector relation.

27.28.1 Rank from singular values

\[ A=U\Sigma V^T, \]

then multiplication by \(V^T\) and \(U\) are invertible orthogonal changes of coordinates. Therefore the rank of \(A\) equals the rank of \(\Sigma\).

The rank of \(\Sigma\) is the number of nonzero diagonal entries.

Thus

\[ \operatorname{rank}(A)=\#\{i:\sigma_i>0\}. \]

27.29 29. Proofs involving algorithms

An algorithm proof usually has two parts:

correctness,
termination or computability.

In linear algebra, algorithm correctness often means showing that each step preserves the desired structure.

27.29.1 Example: row reduction

To justify row reduction for solving \(Ax=b\):

each row operation produces an equivalent system,
equivalent systems have the same solution set,
the final row-reduced system is easier to solve.

27.29.2 Example: Gram–Schmidt

To justify Gram–Schmidt:

each new vector \(u_j\) is formed by subtracting projections onto previous \(q_i\),
therefore \(u_j\) is orthogonal to previous \(q_i\),
normalizing gives \(q_j\) with norm \(1\),
each \(q_j\) remains in the span of \(a_1,\ldots,a_j\),
the spans are preserved.

27.30 30. Counterexamples

A counterexample disproves a universal statement.

To disprove:

\[ \text{For all }x,\ P(x)\text{ is true}, \]

find one \(x\) such that \(P(x)\) is false.

27.30.1 Example

False statement:

If \(AB=0\), then \(A=0\) or \(B=0\).

Counterexample:

\[ A= \begin{bmatrix} 1&0\\ 0&0 \end{bmatrix}, \qquad B= \begin{bmatrix} 0&0\\ 0&1 \end{bmatrix}. \]

Then

\[ AB= \begin{bmatrix} 0&0\\ 0&0 \end{bmatrix}, \]

but neither \(A\) nor \(B\) is the zero matrix.

27.30.2 Common false statements in linear algebra

\(AB=BA\) for all matrices.
If \(AB=0\), then \(A=0\) or \(B=0\).
If \(A^2=I\), then \(A=I\).
If \(A\) and \(B\) are invertible, then \((AB)^{-1}=A^{-1}B^{-1}\).
If vectors span a space, then they are automatically independent.
If vectors are independent, then they automatically span the whole ambient space.
If a matrix has determinant zero, then it is the zero matrix.
If a matrix has repeated eigenvalues, then it is not diagonalizable.
If a matrix is diagonalizable, then it is orthogonally diagonalizable.

Each false statement can be disproved with a carefully chosen example.

27.31 31. Writing clear proofs

A proof should be readable.

27.31.1 Good habits

State what you assume.
State what you want to prove.
Use definitions explicitly.
Keep notation consistent.
Explain why each step follows.
Avoid unnecessary computation.
Use complete sentences around equations.
End by clearly stating the conclusion.

27.31.2 Helpful phrases

“Assume that…”
“We need to show that…”
“By the definition of…”
“Since…”
“Therefore…”
“This implies…”
“Conversely…”
“It remains to show…”
“Thus…”
“Hence the claim follows.”

27.32 32. Common proof mistakes

27.32.1 Mistake 1: proving only one direction of an if-and-only-if statement

For

\[ P\Longleftrightarrow Q, \]

you must prove both directions.

27.32.2 Mistake 2: using what you are trying to prove

Do not assume the conclusion in the middle of the proof.

27.32.3 Mistake 3: checking examples instead of proving a general statement

Examples can suggest a proof, but they do not prove a universal claim.

27.32.4 Mistake 4: ignoring nonzero conditions

Eigenvectors must be nonzero.

Projection formulas require the direction vector to be nonzero.

Inverse formulas require invertibility.

27.32.5 Mistake 5: confusing a vector with its coordinates

A vector and its coordinate representation depend on the chosen basis.

27.32.6 Mistake 6: forgetting dimensions

Before multiplying matrices, check that dimensions match.

Many false arguments fail because a product is not defined.

27.32.7 Mistake 7: assuming commutativity

Usually,

\[ AB\ne BA. \]

Be careful when rearranging matrix products.

27.32.8 Mistake 8: dividing by a vector or matrix

You cannot divide by a vector.

You cannot divide by a matrix. If a matrix is invertible, multiply by its inverse on the correct side.

27.33 33. A proof checklist

Before submitting a proof, ask:

Did I state the assumptions?
Did I state what must be shown?
Did I use the correct definition?
If it is an if-and-only-if proof, did I prove both directions?
If it is a set equality, did I prove both inclusions?
If I used an inverse, did I know the matrix was invertible?
If I used an eigenvector, did I check it was nonzero?
If I multiplied matrices, did the dimensions match?
Did I avoid assuming the conclusion?
Is the conclusion clearly stated?

27.34 34. Practice problems

27.34.1 A. Subspaces

Prove that \(\operatorname{Col}(A)\) is a subspace of \(\mathbb{R}^m\).
Prove that \(\operatorname{Null}(A)\) is a subspace of \(\mathbb{R}^n\).
Give an example of a subset of \(\mathbb{R}^2\) that is closed under addition but not under scalar multiplication.
Give an example of a subset of \(\mathbb{R}^2\) that contains \(0\) but is not a subspace.

27.34.2 B. Linear independence and span

Prove that if a set of vectors contains the zero vector, then it is linearly dependent.
Prove that if \(v_2=cv_1\) for some scalar \(c\), then \(v_1,v_2\) are linearly dependent.
Prove that if \(v_1,\ldots,v_k\) are linearly independent, then none of the vectors can be written as a linear combination of the others.
Prove that if \(v_1,\ldots,v_n\) are independent vectors in \(\mathbb{R}^n\), then they form a basis of \(\mathbb{R}^n\).

27.34.3 C. Matrix transformations

Prove that \(T(x)=Ax\) is linear.
Prove that \(T(x)=Ax+b\) is not linear when \(b\ne 0\).
Prove that the composition of two linear transformations is linear.
Prove that if \(A\) is invertible, then \(T(x)=Ax\) is one-to-one and onto.

27.34.4 D. Orthogonality and projection

Prove the projection formula onto a line.
Prove that a projection matrix \(P\) satisfies \(P^2=P\).
Prove that if \(Q\) has orthonormal columns, then \(QQ^T\) is a projection matrix.
Prove that the least-squares residual is orthogonal to the column space.

27.34.5 E. Eigenvalues and diagonalization

Prove that eigenvectors for distinct eigenvalues are linearly independent.
Prove that if an \(n\times n\) matrix has \(n\) distinct eigenvalues, then it is diagonalizable.
Prove that if \(A=PDP^{-1}\), then \(A^k=PD^kP^{-1}\).
Prove that if \(A\) is triangular, then its eigenvalues are its diagonal entries.

27.34.6 F. Symmetric matrices and quadratic forms

Prove that eigenvectors of a symmetric matrix for distinct eigenvalues are orthogonal.
Prove that \(A^TA\) is symmetric positive semidefinite.
Prove that if all eigenvalues of a symmetric matrix are positive, then the matrix is positive definite.
Prove that if \(A=QDQ^T\), then \(x^TAx=y^TDy\) with \(y=Q^Tx\).

27.34.7 G. SVD

Prove that singular values are nonnegative.
Prove that the rank of \(A\) equals the number of nonzero singular values.
Prove that \(A^TA\) is positive semidefinite.
Prove that if \(Av_i=\sigma_i u_i\), then \(A^Tu_i=\sigma_i v_i\) for positive singular values in the SVD.

27.35 35. Final advice

The best way to learn proofs is to write many of them.

At first, proofs may feel like a different language. Over time, the patterns become familiar.

In linear algebra, most proofs come from a small number of ideas:

use the definition,
solve a homogeneous equation,
show a set is closed under linear combinations,
count dimensions,
prove two inclusions,
use dot products for orthogonality,
use projection for best approximation,
use eigenvector equations for spectral structure,
use orthogonal diagonalization for symmetric matrices,
use \(A^TA\) for singular values.

When stuck, return to the main question:

What does the statement mean in terms of vectors, matrices, subspaces, transformations, or geometry?

A proof is the bridge between meaning and certainty.