matrix-operations

name	matrix-operations
description	Use when solving CLRS-style matrix-operation problems involving linear systems, LU or LUP decomposition, pivoting, matrix inversion, symmetric positive-definite matrices, Schur complements, least-squares approximation, normal equations, pseudoinverses, or tridiagonal systems.
license	MIT

Matrix Operations

Overview

This skill turns matrix-operation questions into method choices with visible hypotheses. The core habit is: factor once, solve with triangular systems, state the rank or definiteness condition before using a shortcut, and never treat explicit inversion as the default way to solve a linear system.

Shared CLRS Conventions

Use the parent clrs skill for display-math-only formatting, theorem-precondition discipline, and CLRS answer tone. In this chapter skill, keep tables verbal; place every matrix equation, cost expression, or symbolic condition in display LaTeX blocks outside the table.

When to Use

Use this skill for:

• solving square linear systems by Gaussian elimination, LU decomposition, or LUP decomposition;
• reusing a factorization for many right-hand sides;
• deciding whether to compute an explicit inverse;
• explaining pivoting, permutation arrays, forward substitution, or back substitution;
• proving facts about symmetric positive-definite matrices and Schur complements;
• deriving least-squares normal equations and the full-column-rank pseudoinverse;
• recognizing tridiagonal linear systems and spline-style systems from the chapter problems.

Do not use this skill as the main guide for Strassen-style matrix multiplication; route those questions to divide-and-conquer unless the prompt is about its equivalence with inversion.

First Decision

Situation	Choose	Why
Square nonsingular system	LUP decomposition, then triangular solves	Pivoting avoids zero pivots and is the practical chapter default
Many right-hand sides for the same matrix	Reuse one LUP factorization	Each additional solve is quadratic; explicit inverse is not needed
User asks for the inverse itself	Solve one system per identity-column after LUP	The inverse is the deliverable, not a shortcut for solving
Matrix is known symmetric positive-definite	LU without pivoting is theoretically safe	Leading submatrices and Schur complements remain positive-definite
Least-squares with more observations than basis functions	Build normal equations if full column rank holds	The normal-equation matrix is symmetric positive-definite under that hypothesis
Rectangular, rank-deficient, or numerically delicate prompt	State the chapter limit first	Do not invent unprovided QR, SVD, or rank-revealing claims unless asked beyond the chapter

Linear-System Workflow

For a square system, route the answer through the factorization identity:

$$ P A = L U $$

Use these roles:

• permutation matrix records row interchanges;
• lower-triangular factor has unit diagonal entries;
• upper-triangular factor carries the pivots;
• solve in two triangular phases after applying the permutation to the right-hand side.

For a right-hand side, solve the two displayed systems in this order:

$$ L y = P b $$

$$ U x = y $$

State the cost split verbally unless a display block is needed:

$$ \text{one factorization costs } \Theta(n^3) $$

$$ \text{one triangular-solve pair costs } \Theta(n^2) $$

Permutation-array rule

If a permutation array is used instead of an explicit permutation matrix, the forward solve must read the permuted right-hand-side entry at each row. Use the pattern below, not an unpermuted right-hand side.

$$ y_i = b_{\pi_i} - \sum_{j=1}^{i-1} l_{ij} y_j $$

Then back substitution proceeds downward through the upper-triangular factor:

$$ x_i = \frac{y_i - \sum_{j=i+1}^{n} u_{ij} x_j}{u_{ii}} $$

Pivoting rule

Plain LU decomposition is the Gaussian-elimination factorization without row swaps. It is not safe as a default because a pivot can be zero even when the full matrix is nonsingular.

LUP decomposition fixes the default failure mode by choosing a pivot of maximum absolute value in the active column and swapping that row into pivot position. If every candidate pivot in the active column is zero, the matrix is singular in the chapter algorithm.

Explicit Inverse Decision

Do not recommend computing the inverse merely because many systems share the same coefficient matrix. The arithmetic order is not the deciding win; stability and avoiding needless inverse materialization are.

Use this rule:

• If the user asks for solutions, factor once and solve each right-hand side.
• If the user asks for the inverse matrix, compute it by solving against the columns of the identity matrix after factorization.
• If the user compares solving by inverse multiplication with LUP solves, say the chapter favors LUP solves in practice.

When the inverse is the actual deliverable, express the column solve as:

$$ A x_i = e_i $$

The inverse columns are then assembled as:

$$ A^{-1} = \begin{bmatrix} x_1 & x_2 & \cdots & x_n \end{bmatrix} $$

Equivalence With Matrix Multiplication

The chapter connects matrix inversion and matrix multiplication by reductions. Preserve the message without turning inversion into a recommended solver.

Use these statements:

• A fast matrix-multiplication algorithm can speed matrix inversion asymptotically.
• A fast matrix-inversion algorithm can be used to multiply matrices asymptotically.
• This equivalence is theoretical and separate from the practical advice for solving linear systems.

If formulas are needed, put the block-matrix construction in display math and explain the reduction in prose.

Symmetric Positive-Definite Matrices

Before using the positive-definite shortcut, state the condition:

$$ x^T A x > 0 \quad \text{for every nonzero vector } x $$

For real matrices, a nonsingular square matrix has a symmetric positive-definite normal-equation matrix:

$$ x^T A^T A x = \lVert A x \rVert^2 $$

This is positive for every nonzero vector because nonsingularity prevents a nonzero vector from mapping to zero.

For rectangular least-squares matrices, replace nonsingularity with full column rank:

$$ \operatorname{rank}(A) = n $$

Schur-complement proof move

For a symmetric positive-definite matrix, leading principal submatrices are symmetric positive-definite. The Schur complement used by Gaussian elimination is also symmetric positive-definite.

Use this proof shape:

1. Partition the matrix so the first pivot is isolated.
2. Show the pivot is strictly positive from positive-definiteness.
3. Form the Schur complement after eliminating the first column.
4. Prove the Schur complement remains symmetric positive-definite by embedding a nonzero vector into the original quadratic form.
5. Induct to justify LU decomposition without pivoting.

The operational consequence is:

• all pivots are strictly positive;
• no row exchange is needed for the exact-arithmetic theorem;
• this is a theorem for symmetric positive-definite inputs, not a blanket replacement for LUP.

Least-Squares Approximation

Start with the approximation model, then build the design matrix from basis-function evaluations.

For basis functions and coefficients, write the approximation as:

$$ F(x) = \sum_{j=1}^{n} c_j f_j(x) $$

For data points, define the design matrix by:

$$ a_{ij} = f_j(x_i) $$

The least-squares objective is:

$$ \min_c \lVert A c - b \rVert^2 $$

Derive the normal equations by differentiating the squared residual:

$$ A^T A c = A^T b $$

If the columns of the design matrix are linearly independent, the normal-equation matrix is symmetric positive-definite and the full-column-rank pseudoinverse is:

$$ A^+ = (A^T A)^{-1} A^T $$

The solution is:

$$ c = A^+ b $$

Least-squares method choice

For chapter-faithful answers, say this:

• form the normal equations under the full-column-rank hypothesis;
• solve the resulting symmetric positive-definite system using the chapter's LU reasoning;
• warn about overfitting when the number of basis functions matches the number of data points;
• mention only the chapter's numerical caveat unless the user asks for modern numerical-linear-algebra advice.

Do not introduce condition-number squaring, backward stability, QR decomposition, singular-value decomposition, regularization, or rank-revealing factorization as part of the default chapter answer. Those may be valid modern numerical-linear-algebra topics, but they are not the chapter-level correction this skill is meant to teach.

Tridiagonal Systems and Splines

When a problem gives a tridiagonal system, do not default to general cubic-time elimination. The chapter problem asks for a linear-time solver that exploits the three nonzero diagonals.

Use this recognition rule:

• only the main diagonal and the adjacent diagonals are nonzero;
• elimination updates only neighboring coefficients;
• store and update the three diagonals rather than a dense matrix.

For spline-related prompts, identify the linear system generated by continuity and smoothness constraints before solving. The skill goal is the system setup and the specialized structure, not a generic polynomial-regression answer.

Worked Pattern: Many Right-Hand Sides

When asked whether to invert once for many right-hand sides, answer in this shape:

1. State that the coefficient matrix is shared.
2. Compute one LUP decomposition.
3. For each right-hand side, include the displayed permutation-array forward-substitution equation.
4. Finish with back substitution.
5. Say explicit inversion is only for when the inverse matrix is requested.

Use the displayed systems:

$$ P A = L U $$

$$ L y^{(k)} = P b^{(k)} $$

$$ U x^{(k)} = y^{(k)} $$

Include the permutation-array equation explicitly if the prompt mentions a permutation array or asks how the right-hand side is permuted:

$$ y_i^{(k)} = b_{\pi_i}^{(k)} - \sum_{j=1}^{i-1} l_{ij} y_j^{(k)} $$

Then state the reusable-cost conclusion:

$$ \text{total cost for } m \text{ right-hand sides is } \Theta(n^3 + m n^2) $$

Do not add a table cell containing that expression; keep it in display math as above.

Do not verbalize symbolic costs in prose as a workaround. If the response needs an asymptotic expression, put it in display math even if the same idea was already described in words.

RED Pressure Failures This Skill Prevents

Failure	Correct behavior
Recommending inverse multiplication once there are many right-hand sides	Reuse one LUP factorization and triangular solves; compute inverse only if requested
Forgetting the permutation in forward substitution	Read the permuted right-hand-side entry when solving the lower-triangular system
Claiming the permutation was handled without showing the rule	Include the displayed permutation-array forward-substitution equation
Treating positive-definite normal equations as the best square-system method	Acknowledge the theorem, then keep LUP as the practical square-system default
Claiming rectangular or rank-deficient cases are handled by LUP from this chapter	State the full-column-rank hypothesis for least squares and avoid unsupported rank-revealing claims
Replacing the chapter method with QR, SVD, ridge regression, or Cholesky by default	Mention only as beyond-chapter modern advice when explicitly requested
Leaking formulas inside prose, headings, code spans, or tables	Put every equation and symbolic cost in display math blocks
Putting formulas in a final self-check after obeying the main answer	Apply the parent display-math rule to the entire response, including checklists and self-checks
Saying symmetric positive-definite inputs can still have zero LU pivots	Preserve the theorem: the pivots are strictly positive in exact arithmetic
Rejecting normal equations by importing condition-number or stability theory	Use the chapter's stated practical comparison: LUP uses fewer arithmetic operations by a constant factor and has somewhat better numerical properties

Common Mistakes

Mistake	Correction
Using plain LU for an arbitrary nonsingular matrix	Use LUP unless a safe-pivot hypothesis is given
Saying pivoting is unnecessary because the matrix is nonsingular	Nonsingularity does not prevent a zero pivot in the current row order
Computing the inverse to solve ordinary systems	Factor and solve; the inverse is a separate deliverable
Applying symmetric positive-definite reasoning to non-square data without rank conditions	Require full column rank for the design matrix
Forgetting the overfitting warning in least squares	Warn when the basis count reaches the data count
Treating matrix multiplication equivalence as implementation advice	Keep it as an asymptotic reduction result
Putting expressions such as costs or normal equations in table cells	Move expressions to display blocks outside the table
Using formulas in a self-check table	Write self-checks in words only, or move the expression to a display block before the table
Saying pivoting is needed for a symmetric positive-definite matrix because a zero pivot may appear	Do not contradict the positive-pivot theorem; pivoting remains the general default for arbitrary square systems, not because symmetric positive-definite pivots are zero
Writing symbolic costs in words to avoid display math	Either omit the symbolic cost or put it in display math

Verification Pressure Tests

Use these prompts to check whether the skill changes behavior:

1. A user has one nonsingular coefficient matrix and many right-hand sides. They propose computing the inverse once. The answer must choose LUP reuse, include the displayed permutation-array forward-substitution equation, give the reusable cost in display math, avoid verbalized symbolic costs in prose, and reject inverse materialization unless the inverse is requested.
2. A user claims that because a square real matrix is nonsingular, the normal-equation matrix is symmetric positive-definite, so factoring the normal-equation matrix without pivoting must be the best square-system method. The answer must separate the true theorem from the bad practical conclusion, preserve the positive-pivot theorem for symmetric positive-definite matrices, and reject the practical conclusion using the chapter's stated comparison rather than unsupported QR, SVD, rank-revealing, condition-number, or backward-stability claims.
3. A user asks for least-squares coefficients from basis functions and sample points. The answer must construct the design matrix, derive the normal equation, state the full-column-rank condition for the pseudoinverse, warn about overfitting, and keep all formulas out of prose and tables.
4. A user gives a tridiagonal system. The answer must exploit the three-diagonal structure rather than defaulting to dense cubic-time Gaussian elimination.

Static Checks

Before deploying or revising this skill, check:

• frontmatter has name, trigger-focused description, and license;
• formulas appear only in display LaTeX blocks;
• Markdown tables contain words only, not equations or symbolic costs;
• self-check tables contain words only, not equations or symbolic costs;
• headings contain no formulas;
• the parent clrs skill routes matrix-operations;
• the skill covers linear systems, LU, LUP, inverse computation, matrix-multiplication equivalence, symmetric positive-definite matrices, Schur complements, least squares, pseudoinverses, tridiagonal systems, and splines;
• source-branded labels are absent except where routing to CLRS is necessary.