Applied Linear Algebra

Lecture 19

Seungook Yu

POSTECH

Spring 2026

Seungook Yu (POSTECH) Applied Linear Algebra Spring 2026 1 / 48

Review: Extending to an Orthonormal Basis

Let W ⊂ Rn with dim(W) = r.

Given a basis
{b1 , . . . , br } of W,

Goal.
Find an orthonormal basis
{w1 , . . . , wn } of Rn
such that
span{w1 , . . . , wj } = span{b1 , . . . , bj } for each j = 1, . . . , r.

Seungook Yu (POSTECH) Applied Linear Algebra Spring 2026 2 / 48

Review: Step 1 (Orthonormal basis of W)
Note that the diagonal cross-filling of
( )
BT B I
M=
I (BT B)−1
gives the diagonal cross-filling of (BT B)−1 in the opposite direction:

∑
r
1
(BT B)−1 = Qj , Qj = dj dT ,
pivotj j
j=1
where dj is the j-th pivot column.

∑
j
dj = (∗, . . . , ∗, 0, . . . , 0)T =⇒ Bdj = dji bi ∈ span{b1 , . . . , bj }.
i=1

Moreover,
span{w1 , . . . , wj } = span{b1 , . . . , bj } for each j = 1, . . . , r.
Seungook Yu (POSTECH) Applied Linear Algebra Spring 2026 3 / 48
Review: Step 2 (Extension)
Let
P = B(BT B)−1 BT = w1 wT T
1 + · · · + wr wr .

Then P is the orthogonal projection with

Col(P) = W = Col(B).

The diagonal cross-filling of I − P gives orthonormal vectors

wr+1 , . . . , wn

such that
span{wr+1 , . . . , wn } = Col(I − P) = Null(P) = W⊥ .

Conclusion.
{w1 , . . . , wn } is an orthonormal basis of Rn .
Seungook Yu (POSTECH) Applied Linear Algebra Spring 2026 4 / 48
Review: Least Squares
Consider
Ax = b, A ∈ Rm×n , b ∈ Rm ,
where A has full column rank.
Definition.
A vector x̂ is a least squares solution if it minimizes

∥b − Ax∥2 .

Equivalently,
let
P = A(AT A)−1 AT
be the orthogonal projection onto Col(A). Then

Ax̂ = Pb.
Seungook Yu (POSTECH) Applied Linear Algebra Spring 2026 5 / 48
Review: Properties of Least Squares

Remark.
If b ∈ Col(A), then
Pb = b ⇒ Ax̂ = b,
so x̂ is an exact solution.
Theorem (Normal Equation).
The least squares solution x̂ satisfies

AT Ax̂ = AT b.

Seungook Yu (POSTECH) Applied Linear Algebra Spring 2026 6 / 48

Review: Linear Regression
Given data
(t1 , y1 ), . . . , (tm , ym ), (m ≥ 2),
finding a best-fitting line
y = f(t) = a + bt
is a least squares problem.

ym

y2 ···
y1

t
t1 t2 ··· tm
Seungook Yu (POSTECH) Applied Linear Algebra Spring 2026 7 / 48
Review: Linear Regression

More precisely,     

y1 = a + bt1
 1 t1 ( ) y1
..  .. ..  a =  ..  .
. ⇐⇒ . . b  . 


y = a + bt 1 tm ym
m m

Let Ax = y, where  
1 t1
 .. .. 
A = . .
1 tm
is the evaluation matrix.
Since t1 , . . . , tm are distinct, A has full column rank.

Seungook Yu (POSTECH) Applied Linear Algebra Spring 2026 8 / 48

Review: Linear Regression

Error.
∑
m
E= (yi − f(ti ))2 = ∥y − Ax∥2 .
i=1

Thus finding a best-fitting line is the problem minimizing

∥y − Ax∥2 .

This is a least squares problem.

Seungook Yu (POSTECH) Applied Linear Algebra Spring 2026 9 / 48

Review: Beyond Lines
Given data
(t1 , y1 ), . . . , (tm , ym ),
we may consider more general models.
Polynomial model.
y = f(t) = a0 + a1 t + · · · + an tn .

Then  
1 t1 ··· tn1
 .. .. ..  ,
A = . . . Ax = y.
1 tm · · · tnm

A is a Vandermonde-type matrix, and if t1 , . . . , tm are distinct and m ≥ n + 1, then A has

full column rank.
Thus finding the best fit is again a least squares problem.
Seungook Yu (POSTECH) Applied Linear Algebra Spring 2026 10 / 48
Review: Other Function Spaces

The same idea works for other families of functions.

Example.
f(t) = a sin t + b cos t.

Then the evaluation matrix is

 
sin t1 cos t1
 .. ..  ,
A= . .  Ax = y.
sin tm cos tm

Again, we solve the least square problem minimizing

∥y − Ax∥2 .

Seungook Yu (POSTECH) Applied Linear Algebra Spring 2026 11 / 48

Outline

1 Review

2 Determinant

3 Switching Matrices

4 Computing Determinants via Cross-Filling

Seungook Yu (POSTECH) Applied Linear Algebra Spring 2026 12 / 48

Definition of Determinant
Definition.
A function
det : {square matrices} → R
is called a determinant if it satisfies the following properties.
P1. Multilinearity.
det(A) is linear in each column separately.
P2. Alternating.
If two columns of A are equal, then
det(A) = 0.

P3. Normalization.

det(I) = 1.

Seungook Yu (POSTECH) Applied Linear Algebra Spring 2026 13 / 48

Understanding the Definition

Let A = (a1 , . . . , an ) be a matrix with columns ai .

Multilinearity.
For any column aj = αv + βw,

det(a1 , . . . , aj , . . . , an ) = α det(a1 , . . . , v, . . . , an ) + β det(a1 , . . . , w, . . . , an ).

Alternating.
If two columns are equal, then

det(a1 , . . . , v, . . . , v, . . . , an ) = 0.

Seungook Yu (POSTECH) Applied Linear Algebra Spring 2026 14 / 48

Common Mistake: Additivity

Wrong intuition.
det(A + B) = det(A) + det(B) (false)

Example. ( ) ( ) ( )
1+2 1+3 1 1 2 3
= + .
2+1 3+2 2 3 1 2

Correct rule (multilinearity).

det(v1 + w1 , v2 + w2 )
= det(v1 , v2 ) + det(v1 , w2 ) + det(w1 , v2 ) + det(w1 , w2 ).

Seungook Yu (POSTECH) Applied Linear Algebra Spring 2026 15 / 48

Common Mistake: Scaling

Wrong intuition.
det(kA) = k det(A) (false)

Correct rule.
If A is an n × n matrix, then
det(kA) = kn det(A).

Example.
det(−A) = (−1)n det(A).

Reason.
Each column is multiplied by k, so

det(ka1 , . . . , kan ) = kn det(a1 , . . . , an ).

Seungook Yu (POSTECH) Applied Linear Algebra Spring 2026 16 / 48

Zero Column
Proposition.
If a square matrix has a zero column, then
det(A) = 0.

Proof.
Suppose the j-th column is zero:
A = (a1 , . . . , 0, . . . , an ).
Since
0 = 0v
for any vector v, multilinearity gives
det(a1 , . . . , 0, . . . , an ) = det(a1 , . . . , 0v, . . . , an )
= 0 det(a1 , . . . , v, . . . , an ) = 0.
□
Seungook Yu (POSTECH) Applied Linear Algebra Spring 2026 17 / 48
Swapping Columns

Proposition.
Swapping two columns changes the sign of the determinant.
Proof.

0 = det(. . . , ai + aj , . . . , ai + aj , . . . )

= det(. . . , ai , . . . , aj , . . . ) + det(. . . , aj , . . . , ai , . . . )

Thus
det(. . . , ai , . . . , aj , . . . ) = − det(. . . , aj , . . . , ai , . . . ).
□

Seungook Yu (POSTECH) Applied Linear Algebra Spring 2026 18 / 48

Column Replacement
Proposition.
Column replacement does not change the determinant.
More precisely, if i ̸= j, then
det(a1 , . . . , ai − λaj , . . . , aj , . . . , an ) = det(a1 , . . . , ai , . . . , aj , . . . , an ).

Proof.
By multilinearity in the i-th column,
det(. . . , ai − λaj , . . . , aj , . . . )
= det(. . . , ai , . . . , aj , . . . ) − λ det(. . . , aj , . . . , aj , . . . ).

The second term is zero by alternating. Hence

det(. . . , ai − λaj , . . . , aj , . . . ) = det(. . . , ai , . . . , aj , . . . ).
□
Seungook Yu (POSTECH) Applied Linear Algebra Spring 2026 19 / 48
Example: Column Replacement

( )
1 3
det
2 5
( )
a2 →a2 −3a1 1 0
= det
2 −1
( )
a1 →a1 +2a2 1 0
= det
0 −1
( )
1 0
= − det = −1
0 1

Seungook Yu (POSTECH) Applied Linear Algebra Spring 2026 20 / 48

Linear Dependence and Determinant

Proposition.
If the columns of A are linearly dependent, then det(A) = 0.
Proof. ∑
If ak = i̸=k λi ai , define A′ by
∑
ak → ak − λi ai = 0.
i̸=k

Then det(A′ ) = det(A) and A′ has a zero column.

Thus det(A) = 0.
□

Seungook Yu (POSTECH) Applied Linear Algebra Spring 2026 21 / 48

Determinant of a 2 × 2 Matrix
Let ( )
a b
A= .
c d
Write the columns as ( ) ( )
a b
= ae1 + ce2 , = be1 + de2 .
c d
By multilinearity,
det(A) = det(ae1 + ce2 , be1 + de2 )
= ab det(e1 , e1 ) + ad det(e1 , e2 ) + bc det(e2 , e1 ) + cd det(e2 , e2 ).
By alternating and normalization,
det(e1 , e1 ) = 0, det(e2 , e2 ) = 0, det(e1 , e2 ) = 1, det(e2 , e1 ) = −1.

Thus
det(A) = ad − bc.
Seungook Yu (POSTECH) Applied Linear Algebra Spring 2026 22 / 48
Geometric Interpretation of Determinant
Let ( ) ( ) ( )
a b a b
A= , v1 = , v2 = .
c d c d

v2

v1

Geometric meaning.
det(A) = signed area of the parallelogram spanned by v1 , v2 .
Seungook Yu (POSTECH) Applied Linear Algebra Spring 2026 23 / 48
Orientation and Sign

Normalization.
det(I2 ) = det(e1 , e2 ) = 1.

Swapping columns gives

det(e2 , e1 ) = −1.

Interpretation.
The sign of the determinant is determined by orientation:
(e1 , e2 ) : counterclockwise ⇒ +
(e2 , e1 ) : clockwise ⇒ −

Thus det(v1 , v2 ) is a signed area.

Seungook Yu (POSTECH) Applied Linear Algebra Spring 2026 24 / 48

Area of a Parallelogram

Let ( ) ( )
a b
v1 = , v2 = .
c d

The area of the parallelogram spanned by v1 , v2 is

Area = (a + b)(c + d) − ac − bd − 2bc.

Thus
Area = ad − bc.

Conclusion. ( )
a b
det = ad − bc.
c d

Seungook Yu (POSTECH) Applied Linear Algebra Spring 2026 25 / 48

Geometric Meaning of Additivity

Additivity in the first column.

det(v1 + w1 , v2 ) = det(v1 , v2 ) + det(w1 , v2 ).

v2
w1
v1 v1 + w1

The large parallelogram is decomposed into two parallelograms.

Seungook Yu (POSTECH) Applied Linear Algebra Spring 2026 26 / 48

Geometric Meaning of Scaling

Scaling in the first column.

det(kv1 , v2 ) = k det(v1 , v2 ).

v2

v1 kv1

Scaling one side by k scales the signed area by k.

Seungook Yu (POSTECH) Applied Linear Algebra Spring 2026 27 / 48

Geometric Meaning of Alternating
Alternating.
If two columns are equal, then
det(v, v) = 0.

area = 0

The parallelogram spanned by v and v collapses to a line segment.

Therefore,
det(v, v) = 0.
Seungook Yu (POSTECH) Applied Linear Algebra Spring 2026 28 / 48
Determinant for n = 3
Let  
a b c
A = d e f  .
g h i

Write each column as a combination of e1 , e2 , e3 .

By multilinearity, we obtain many terms.
Alternating removes all repeated indices.
Thus only terms using each of e1 , e2 , e3 exactly once survive:

det(A) = aei det(e1 , e2 , e3 ) + afh det(e1 , e3 , e2 )

+ bdi det(e2 , e1 , e3 ) + bfg det(e2 , e3 , e1 )
+ cdh det(e3 , e1 , e2 ) + ceg det(e3 , e2 , e1 ).

Seungook Yu (POSTECH) Applied Linear Algebra Spring 2026 29 / 48

General Case

For an n × n matrix
∑
n
A = (a1 , . . . , an ), aj = aij ei ,
i=1

multilinearity gives a sum of many terms.

Only terms with distinct basis vectors survive.
Thus ∑
det(A) = (products of entries) · det(ei1 , . . . , ein ),
where (i1 , . . . , in ) are all distinct.
These correspond to permutations of {1, . . . , n}.

Seungook Yu (POSTECH) Applied Linear Algebra Spring 2026 30 / 48

Zero Row

Proposition.
If a square matrix has a zero row, then

det(A) = 0.

Reason.
In the determinant formula, each surviving term chooses exactly one entry from each row.
Therefore, every term contains one entry from the zero row.
Since all entries in that row are zero, every term is zero.
Thus
det(A) = 0.
□

Seungook Yu (POSTECH) Applied Linear Algebra Spring 2026 31 / 48

Switching Matrices
Definition.
A square matrix is called a switching matrix if

each row and each column has exactly one 1,

and all other entries are 0.
Examples.  
( ) ( ) 1 0 0
1 0 0 1 0 0 1
, ,
0 1 1 0
0 1 0
 
0 0 1 0
0 0 0 1
 .
0 1 0 0
1 0 0 0

Seungook Yu (POSTECH) Applied Linear Algebra Spring 2026 32 / 48

Switching Matrices and Determinants
A switching matrix is exactly a matrix of the form
(ei1 , ei2 , . . . , ein ),
where each of
e1 , . . . , en
appears exactly once.
These are precisely the matrices appearing in the determinant formula:
det(ei1 , ei2 , . . . , ein ).

Every switching matrix can be obtained from the identity matrix

I = (e1 , e2 , . . . , en )
by finitely many column switchings.
Therefore,
det(ei1 , ei2 , . . . , ein ) = ± det(I) = ±1.
Seungook Yu (POSTECH) Applied Linear Algebra Spring 2026 33 / 48
Parity of Column Switchings

There may be many different ways to obtain the same switching matrix from the identity
matrix by column switchings.
However, the parity of the number of switchings is always the same.
That is, for a fixed switching matrix,

the number of switchings is always either even or odd.

Hence
{
+1, if it is obtained by an even number of switchings,
det(ei1 , ei2 , . . . , ein ) =
−1, if it is obtained by an odd number of switchings.

Seungook Yu (POSTECH) Applied Linear Algebra Spring 2026 34 / 48

Zigzag Method

Let S be an n × n switching matrix.

Step 1.
Draw horizontal and vertical line segments connecting each entry 1 to the diagonal entries.
Step 2.
Count the number m of connected loops.
Step 3.
Then
det(S) = (−1)n−m .

Seungook Yu (POSTECH) Applied Linear Algebra Spring 2026 35 / 48

Examples

 
0 0 1 0
0 0 0 1
S=
0
 (n = 4, m = 1) ⇒ det(S) = (−1)4−1 = −1
1 0 0
1 0 0 0

 
0 1 0 0
1 0 0 0
S=
0
 (n = 4, m = 2) ⇒ det(S) = (−1)4−2 = 1
0 0 1
0 0 1 0

S = In (n = m) ⇒ det(In ) = (−1)n−n = 1

Seungook Yu (POSTECH) Applied Linear Algebra Spring 2026 36 / 48

Why This Definition Works
For a switching matrix S, define
det(S) = (−1)n−m ,
where m is the number of loops.
Key observation.
m = n for In (each diagonal entry forms a loop)
1≤m≤n

Effect of column switching.

Switching two columns within a loop increases m by 1
Thus each switching flips the sign of (−1)n−m

Therefore, this definition is consistent with

det(after one swap) = − det(before).

Seungook Yu (POSTECH) Applied Linear Algebra Spring 2026 37 / 48

Example: Cross-Filling

 
2 1 2
A = 1 3 1
2 1 4

Pivot (2, 1) = 1:    
2 6 2 0 −5 0
A = 1 3 1 + 0 0 0
2 6 2 0 −5 2
   
2 −5 0 0 −5 0
det(A) = det 1 0 0 = det 1 0 0
2 −5 2 0 −5 2

Seungook Yu (POSTECH) Applied Linear Algebra Spring 2026 38 / 48

Iteration
 
0 −5 0
Â1 = 1 0 0
0 −5 2

Pivot (1, 2) = −5:

   
0 −5 0 0 1 0
det(Â1 ) = det 1 0 0 = (−5) det(Â2 ), Â2 = 1 0 0
0 −5 2 0 0 2

Pivot (3, 3) = 2:  
0 1 0
det(Â2 ) = 2 det(Â3 ), Â3 = 1 0 0
0 0 1

Seungook Yu (POSTECH) Applied Linear Algebra Spring 2026 39 / 48

Final Step

We obtain
det(A) = (−5) · 2 · det(Â3 ).

Here Â3 is a switching matrix S.

Using the zigzag method:

n = 3, m=2 ⇒ det(S) = (−1)3−2 = −1.

Therefore
det(A) = (−5) · 2 · (−1) = 10.

Seungook Yu (POSTECH) Applied Linear Algebra Spring 2026 40 / 48

Annotated Matrix

Let A be an n × n matrix.
Applying cross-filling successively, we obtain matrices

Â1 , Â2 , . . . , Âk , . . .

Definition.
We call Âk the annotated matrix at step k, i.e., the matrix obtained by replacing each pivot
entry by 1.
Thus Âk records the pivot structure of A.

Seungook Yu (POSTECH) Applied Linear Algebra Spring 2026 41 / 48

Determinant Relation

Theorem.
At each step,
det(Âk−1 ) = pk det(Âk ),
where pk is the k-th pivot.
Thus each pivot contributes multiplicatively to the determinant.

Seungook Yu (POSTECH) Applied Linear Algebra Spring 2026 42 / 48

Determinant Formula

Theorem.
Let rank(A) = r and let
p1 , . . . , pr
be the pivots obtained by cross-filling.
Then
det(A) = p1 p2 · · · pr det(Âr ).

Seungook Yu (POSTECH) Applied Linear Algebra Spring 2026 43 / 48

Determinant and Invertibility
Theorem. For a square matrix A,
A is invertible ⇐⇒ det(A) ̸= 0.

Proof.
Let rank(A) = r.

det(A) = p1 · · · pr det(Âr ).
If r < n, then Âr has a zero column, so
det(A) = 0.
If r = n, then Ân = S is a switching matrix, so
det(A) = p1 · · · pn det(S) ̸= 0.

Thus
det(A) ̸= 0 ⇐⇒ r=n ⇐⇒ A is invertible.
Seungook Yu (POSTECH) Applied Linear Algebra Spring 2026 44 / 48
In Practice
Record only pivots and positions.
 
2 3 1
A = 1 1 2
3 2 1

p1 = 1 (2, 1), p2 = 1 (1, 2), p3 = −8 (3, 3)

 
0 1 0
S = 1 0 0 
0 0 1

det(A) = 1 · 1 · (−8) · (−1) = 8

Seungook Yu (POSTECH) Applied Linear Algebra Spring 2026 45 / 48

Transpose and Determinant
Theorem.
det(A) = det(AT ).

Proof.
If rank(A) < n, then
det(A) = det(AT ) = 0.

If rank(A) = n, using the same pivots in cross-filling,

det(A) = p1 · · · pn det(S), det(AT ) = p1 · · · pn det(ST ),
where S, ST are switching matrices.
Since S and ST have the same number of loops,
det(S) = det(ST ).

Thus det(A) = det(AT ).

□
Seungook Yu (POSTECH) Applied Linear Algebra Spring 2026 46 / 48
Consequences for Rows
Conclusion.
All statements about columns also hold for rows.
In particular:
Row operations preserve the determinant.
If two rows are equal, then
det(A) = 0.
Swapping two rows changes the sign:
det(after swap) = − det(before).

If the rows are linearly dependent, then

det(A) = 0.

Reason.
Apply the corresponding column statements to AT .
Seungook Yu (POSTECH) Applied Linear Algebra Spring 2026 47 / 48
 Thank you

Seungook Yu (POSTECH) Applied Linear Algebra Spring 2026 48 / 48