Seyed Masoud Hosseini · Overview · Study log · Weekly summaries · Ideas · Search · Transcript · RSS feed

Matrix Methods for Data Analysis & ML · Lecture 5 of 36 · 49:24

Lecture 3: Orthonormal Columns Give Q'Q = I

3. Orthonormal Columns in Q Give Q'Q = I on YouTube

Study guide

What this lecture covers

This lecture is a tour of orthogonal matrices, the matrices Strang calls the queens of linear algebra. Starting from the defining property Q^T Q = I, he shows why orthogonal matrices preserve vector length, then works through a gallery of examples: rotation and reflection matrices, Householder reflections, Hadamard-style plus-minus-one matrices, and Haar wavelet matrices.

The lecture closes by connecting orthogonal matrices to eigenvectors, previewing the discrete Fourier transform as the eigenvector matrix of a permutation matrix. After watching, you should be able to verify whether a matrix is orthogonal, explain why orthogonal matrices don't cause numerical overflow, and recognize several standard families of orthogonal matrices by construction.

Key ideas

  • Q^T Q = I for orthonormal columns: this single identity captures both that each column has length 1 and that different columns are perpendicular.
  • Length preservation: ||Qx|| = ||x|| for any vector x, proven directly from Q^T Q = I, which is why orthogonal matrices avoid overflow or underflow in numerical computation.
  • Rotations and reflections: the 2x2 matrix with columns [cos θ, sin θ] and [-sin θ, cos θ] rotates the plane; swapping the sign on the second column instead gives a reflection matrix.
  • Householder reflections: H = I - 2uu^T for a unit vector u is both symmetric and orthogonal, and is used in numerical linear algebra as an alternative to Gram-Schmidt.
  • Hadamard-style matrices: square matrices of plus and minus ones with orthogonal columns can be built recursively (doubling in size), though whether one exists for every size divisible by four remains an open conjecture.
  • Haar wavelets: an orthogonal matrix built from rescaled patterns of 1, -1, and 0 that captures averages and differences at multiple scales.
  • Orthogonal eigenvectors: the eigenvectors of a symmetric matrix, and also of an orthogonal matrix, are automatically orthogonal; the eigenvectors of a permutation matrix give the discrete Fourier transform.

Walkthrough

Why Q'Q = I preserves length (0:01)

Strang defines Q as a matrix with orthonormal columns and shows Q^T Q = I follows directly from the columns being unit length and mutually perpendicular. He then proves ||Qx|| = ||x|| for any x by expanding (Qx)^T(Qx) and using Q^T Q = I, explaining that this length preservation is why numerical algorithms favor orthogonal matrices wherever possible.

Rotation and reflection matrices (3:03)

Working with 2x2 examples, Strang shows that [cos θ, -sin θ; sin θ, cos θ] rotates the whole plane by angle theta, while changing the sign pattern to [cos θ, sin θ; sin θ, -cos θ] produces a reflection matrix instead, with a determinant of -1. He illustrates both by tracking where the standard basis vectors land.

Householder reflections (15:21)

For a unit vector u, Strang defines H = I - 2uu^T and verifies by direct calculation that H is both symmetric and orthogonal (H^2 = I). He notes these matrices are practically important in numerical linear algebra as an alternative to Gram-Schmidt for producing orthogonal matrices.

Hadamard and Haar wavelet matrices (20:26)

Strang builds Hadamard-style matrices of plus and minus ones recursively, doubling from a 2x2 block to 4x4, 8x8, and beyond, and mentions the open conjecture that such matrices exist for every size divisible by four. He then constructs the Haar wavelet matrix, whose columns represent averages and differences at successively finer scales, noting that Haar's simple construction predates the general theory of wavelets by decades, with major later advances credited to Ingrid Daubechies.

Orthogonal eigenvectors and the Fourier matrix (35:43)

Strang closes by noting that eigenvectors of a symmetric matrix, and separately of an orthogonal matrix, are always orthogonal to each other. He builds the eigenvectors of a permutation matrix explicitly using powers of i, showing this produces the columns of the discrete Fourier transform matrix, and cautions that checking orthogonality for complex vectors requires the complex conjugate rather than a plain dot product.

Before you watch

  • Watch Lectures 1 and 2 first: this lecture assumes familiarity with column space, rank, and the factorizations introduced there.
  • Basic comfort with complex numbers (i, powers of i, complex conjugates) is needed for the closing Fourier matrix discussion.

Check your understanding

  1. Why does Q^T Q = I imply that Qx has the same length as x?
  2. What is the geometric difference between the rotation matrix and the reflection matrix built from cos θ and sin θ?
  3. How does a Householder matrix H = I - 2uu^T manage to be both symmetric and orthogonal?
  4. What pattern lets Hadamard-style matrices be built recursively, and what remains unresolved about their existence?
  5. Why must checking orthogonality of complex eigenvectors use the complex conjugate rather than a standard dot product?

Vocabulary

tour (noun)
A trip through several examples or topics, one after another.
This lecture is a tour of orthogonal matrices.
orthogonal matrix (noun)
A square matrix whose columns are unit length and perpendicular to each other.
The queens of linear algebra are orthogonal matrices.
orthonormal (adjective)
Describes a set of vectors that are all unit length and perpendicular to each other.
The columns of Q are orthonormal.
identity matrix (noun)
A square matrix with 1s on the diagonal and 0s everywhere else.
Q^T Q equals the identity matrix.
transpose (noun)
A matrix formed by flipping rows and columns.
Q^T is the transpose of Q.
perpendicular (adjective)
At a right angle to something else.
The columns of an orthogonal matrix are perpendicular to each other.
preserve (verb)
To keep something unchanged.
An orthogonal matrix preserves the length of a vector.
overflow (noun)
An error that happens when a number becomes too large for the computer to store.
Orthogonal matrices help numerical methods avoid overflow.
underflow (noun)
An error that happens when a number becomes too small for the computer to represent accurately.
Keeping lengths fixed also protects against underflow.
rotation matrix (noun)
A matrix that turns every vector by a fixed angle without changing its length.
Multiplying by the rotation matrix spins the plane by theta.
reflection matrix (noun)
A matrix that flips vectors across a line or plane, like a mirror.
Changing one sign turns the rotation matrix into a reflection matrix.
determinant (noun)
A single number computed from a square matrix that tells you facts like whether it can be inverted.
A reflection matrix has determinant -1.
Householder reflection (noun)
A specific type of reflection matrix built from a single unit vector, used in numerical computing.
H = I - 2uu^T is a Householder reflection.
unit vector (noun)
A vector with length exactly 1.
Householder reflections are built from a unit vector u.
symmetric (adjective)
Describes a matrix that stays the same when you flip its rows and columns.
A Householder matrix is both symmetric and orthogonal.
alternative (noun)
A different option that can be used instead of something else.
Householder reflections are an alternative to Gram-Schmidt.
recursively (adverb)
Built step by step, where each new step uses the result of the previous one.
Hadamard matrices can be built recursively by doubling in size.
conjecture (noun)
A mathematical statement believed to be true but not yet proven.
It's an open conjecture that Hadamard matrices exist for every size divisible by four.
wavelet (noun)
A short wave-like pattern used to capture both average and detail information in data.
Haar wavelets capture averages and differences at different scales.
rescale (verb)
To multiply a number or vector so it has a new, more useful size.
Each Haar wavelet column is rescaled to have length 1.
scale (noun)
A level of detail or zoom, from broad to fine.
Haar wavelets work at multiple scales, from coarse to fine.
predate (verb)
To exist or happen before something else in time.
Haar's construction predates the general theory of wavelets.
eigenvector (noun)
A special vector that a matrix only stretches or shrinks, without changing its direction.
Eigenvectors of a symmetric matrix are always orthogonal.
permutation matrix (noun)
A matrix that reorders the entries of a vector without changing their values.
The eigenvectors of a permutation matrix give the Fourier matrix.
Fourier matrix (noun)
A special matrix whose columns are used to break a signal into its frequency parts.
The discrete Fourier transform uses the Fourier matrix.
complex conjugate (noun)
A complex number with the sign of its imaginary part flipped.
Checking orthogonality of complex vectors needs the complex conjugate.
dot product (noun)
The sum of the products of matching entries of two vectors, used to measure angle and length.
A plain dot product isn't enough for complex vectors.

Chapters

From the YouTube description

MIT 18.065 Matrix Methods in Data Analysis, Signal Processing, and Machine Learning, Spring 2018
Instructor: Gilbert Strang
View the complete course: https://ocw.mit.edu/18-065S18
YouTube Playlist: https://www.youtube.com/playlist?list=PLUl4u3cNGP63oMNUHXqIUcrkS2PivhN3k

This lecture focuses on orthogonal matrices and subspaces. Professor Strang reviews the four fundamental subspaces: column space C(A), row space C (A^T), nullspace N(A), left nullspace N (A^T).

License: Creative Commons BY-NC-SA
More information at https://ocw.mit.edu/terms
More courses at https://ocw.mit.edu

← Lecture 2: Multiplying and Factoring Matrices · Lecture 4: Eigenvalues and Eigenvectors →