Linear Algebra and Matrix Computation

Introduction

Linear algebra studies vectors, matrices, linear transformations, and the spaces on which they operate. It is one of the central mathematical languages of computer science. Computer graphics uses matrices to rotate, scale, and project objects; network analysis represents connections with adjacency matrices; machine learning stores data and model parameters as vectors and matrices; and dimensionality-reduction methods identify informative directions in high-dimensional data.

A computer scientist must understand not only how to perform matrix operations, but also what those operations mean, when they are valid, how numerical algorithms behave, and how results should be interpreted. This chapter develops those foundations and connects them to practical computational problems.

Learning Objectives

By the end of this chapter, you should be able to:

• represent data and transformations using vectors and matrices;
• perform matrix operations and interpret their dimensions;
• formulate and solve linear systems;
• explain span, linear independence, basis, dimension, rank, and null space;
• use inner products, norms, orthogonality, and projections;
• compute and interpret eigenvalues and eigenvectors;
• explain the principles of QR factorization and singular value decomposition;
• apply linear algebra to graphics, networks, machine learning, and dimensionality reduction;
• identify numerical, modeling, ethical, and practical limitations.

1. Vectors, Matrices, and Their Interpretation

A vector is an ordered list of numbers. A column vector with n entries belongs to the real vector space ℝⁿ:

The entries may represent coordinates, features, physical quantities, or state variables. For example, a student-record vector might contain age, number of completed credits, average grade, and attendance rate. The interpretation depends on the application; the same mathematical structure can represent very different objects.

A matrix is a rectangular array of numbers. An m × n matrix has m rows and n columns:

The symbol aᵢⱼ denotes the entry in row i and column j. A matrix can represent a data table, a system of equations, a graph, or a linear transformation.

Basic operations

Vectors of the same dimension can be added componentwise. For x, y ∈ ℝⁿ and scalar α:

The dot product, or inner product, is

For real vectors, the Euclidean norm is

The norm measures length. It is nonnegative, equals zero only for the zero vector, and satisfies the triangle inequality.

Matrix addition requires equal dimensions and is componentwise. Matrix multiplication is defined when the inner dimensions agree. If A is m × n and B is n × p, then AB is m × p, with entries

Matrix multiplication is associative, (AB)C = A(BC), and distributive over addition, but it is generally not commutative: AB ≠ BA in general.

For an m × n matrix A and vector x ∈ ℝⁿ, Ax is a vector in ℝᵐ. Thus A defines a mapping from ℝⁿ to ℝᵐ. The jth column of A is the output produced when A acts on the jth standard basis vector.

Worked example: matrix–vector multiplication

Let

Then

The dimensions are compatible: A is 2 × 2 and x is 2 × 1, so the result is 2 × 1.

2. Linear Transformations and Important Matrix Types

A function T: ℝⁿ → ℝᵐ is linear if

for all vectors x, y and scalars α, β. Every linear transformation in finite-dimensional coordinate spaces can be represented by a matrix.

Important matrix types include:

The transpose Aᵀ exchanges rows and columns. If A is m × n, then Aᵀ is n × m. A square matrix A is invertible if there exists A⁻¹ such that

Only square nonsingular matrices have ordinary two-sided inverses. Numerically, one should usually solve Ax = b directly rather than explicitly computing A⁻¹, because factorization-based solving is generally more efficient and stable.

The determinant is defined only for square matrices. For a 2 × 2 matrix,

A square matrix is invertible exactly when its determinant is nonzero. Geometrically, the absolute determinant gives the volume-scaling factor of the transformation; a negative determinant also indicates orientation reversal. For large systems, determinants are usually not the preferred computational tool for solving equations.

3. Linear Systems and Computational Solution

A linear system can be written compactly as

where A is an m × n coefficient matrix, x ∈ ℝⁿ is the unknown vector, and b ∈ ℝᵐ is the right-hand-side vector. The system may have no solution, exactly one solution, or infinitely many solutions.

Gaussian elimination

Gaussian elimination transforms the augmented matrix [A | b] using elementary row operations:

1. interchange two rows;
2. multiply a row by a nonzero scalar;
3. add a multiple of one row to another row.

These operations preserve the solution set. The process produces row-echelon form, after which back substitution determines the unknowns. Partial pivoting selects a sufficiently large pivot and swaps rows when necessary, reducing the risk of numerical error.

Worked example

Consider

The augmented matrix is

Replace the first row by the first row minus twice the second row:

Thus y = 1, and the second original equation gives x − 1 = 1, so x = 2. The solution is (x, y) = (2, 1).

Rank and consistency

The rank of A is the dimension of its column space, equivalently the number of pivots in a row-echelon form. A system Ax = b is consistent exactly when

If the system is consistent and has n unknowns, then it has a unique solution when rank(A) = n. If the rank is less than n, free variables produce infinitely many solutions.

For an underdetermined system, the general solution can be written as a particular solution plus any vector in the null space:

For an overdetermined system, exact consistency may fail. A least-squares solution minimizes the residual norm:

If the columns of A are linearly independent, the normal equations are

However, forming AᵀA can worsen conditioning. QR factorization is generally preferred in reliable numerical software.

4. Vector Spaces, Span, Basis, and Dimension

A vector space is a set closed under vector addition and scalar multiplication and satisfying the usual algebraic rules. Subspaces include lines through the origin, planes through the origin, column spaces, row spaces, and null spaces.

The span of vectors v₁, …, vₖ is the set of all linear combinations:

The vectors are linearly independent if

implies c₁ = ⋯ = cₖ = 0. A basis is a linearly independent spanning set. The number of vectors in any basis of a finite-dimensional space is its dimension.

The four fundamental subspaces of an m × n matrix A are:

• the column space Col(A) ⊆ ℝᵐ;
• the null space Null(A) = {x ∈ ℝⁿ : Ax = 0};
• the row space, a subspace of ℝⁿ;
• the left null space Null(Aᵀ), a subspace of ℝᵐ.

The rank–nullity theorem states

where n is the number of columns of A and nullity(A) is the dimension of Null(A). This theorem links the number of independent directions preserved by A with the number of directions mapped to zero.

5. Orthogonality and Projection

Two vectors are orthogonal when their inner product is zero:

An orthonormal set consists of mutually orthogonal unit vectors. If Q has orthonormal columns, then QᵀQ = I. Orthonormal bases are computationally valuable because coordinates can be obtained by inner products and numerical errors are better controlled.

The projection of a vector b onto a nonzero vector a is

The denominator is nonzero because a ≠ 0. The projection is the closest point to b on the line spanned by a. The residual b − projₐ(b) is orthogonal to a.

For a subspace with orthonormal basis columns in Q, the projection of b onto Col(Q) is

For a full-column-rank matrix A whose columns are not necessarily orthonormal, the projection onto Col(A) is

provided AᵀA is invertible. This formula is mathematically valid under the stated rank condition, but QR or SVD methods are usually safer computationally.

Worked projection example

Let a = [1, 2]ᵀ and b = [3, 1]ᵀ. Then aᵀb = 5 and aᵀa = 5. Therefore

The residual is [3, 1]ᵀ − [1, 2]ᵀ = [2, −1]ᵀ. Its dot product with a is 2 − 2 = 0, confirming orthogonality.

6. Eigenvalues and Eigenvectors

For a square matrix A, a nonzero vector v is an eigenvector with eigenvalue λ if

The transformation changes the length and possibly direction of v, but does not rotate it away from its eigenvector direction. Eigenvalues satisfy the characteristic equation

For a 2 × 2 matrix, this produces a quadratic equation. Eigenvectors are found by solving (A − λI)v = 0 for each eigenvalue.

Worked example

Let

The characteristic equation is

Thus λ = 3 or λ = 1. For λ = 3, an eigenvector is [1, 1]ᵀ. For λ = 1, an eigenvector is [1, −1]ᵀ. These vectors are orthogonal, as expected for a real symmetric matrix.

A matrix is diagonalizable if it has a basis of eigenvectors. Then

where the columns of P are eigenvectors and D is diagonal with corresponding eigenvalues. If A is symmetric, the spectral theorem gives the stronger decomposition

where Q is orthogonal and Λ is diagonal with real eigenvalues.

Eigenvalues help analyze repeated application of a transformation. In a dynamical system xₜ₊₁ = Axₜ, eigenvalues with magnitude greater than one can produce growth, while eigenvalues with magnitude less than one produce decay, subject to diagonalizability and other structural conditions.

7. Matrix Factorizations

Factorizations rewrite a matrix as a product of simpler matrices. They are central to efficient and stable computation.

LU factorization

For suitable square matrices, Gaussian elimination produces

where P is a permutation matrix, L is lower triangular, and U is upper triangular. To solve Ax = b, solve Ly = Pb by forward substitution and then Ux = y by back substitution. LU is useful when the same A is used with many right-hand sides.

QR factorization

A matrix A with independent columns can be factored as

where Q has orthonormal columns and R is upper triangular. QR supports least-squares computation: minimizing ‖Ax − b‖₂ is equivalent to minimizing ‖Rx − Qᵀb‖₂. Householder transformations are generally more stable than naive classical Gram–Schmidt orthogonalization.

Singular value decomposition

Every real m × n matrix has an SVD:

where U and V have orthonormal columns or form orthogonal square matrices, and Σ contains nonnegative singular values σ₁ ≥ σ₂ ≥ ⋯ ≥ 0. The singular values are the square roots of the eigenvalues of AᵀA.

The SVD reveals the most important input and output directions of a linear transformation. A rank-k approximation is

where only the k largest singular values and corresponding vectors are retained. The Eckart–Young theorem states that this is a best rank-k approximation in the usual Frobenius norm and spectral norm senses.

SVD underlies principal component analysis, recommender systems, image compression, latent semantic analysis, and the computation of the Moore–Penrose pseudoinverse. If A = UΣVᵀ, then, for nonzero singular values,

where Σ⁺ replaces each nonzero σᵢ by 1/σᵢ and transposes the rectangular arrangement. The pseudoinverse provides minimum-norm solutions for underdetermined systems and least-squares solutions for inconsistent systems.

8. Applications in Computer Science

Computer graphics

Points in two-dimensional graphics can be represented as vectors. A scaling transformation is

and a rotation through angle θ is

The angle is measured in radians or degrees consistently with the trigonometric implementation. Applying R(θ)x rotates x counterclockwise in a standard Cartesian coordinate system. In three-dimensional graphics, homogeneous coordinates use 4 × 4 matrices so that translations, rotations, scaling, and perspective transformations can be composed through matrix multiplication.

Networks and graphs

For a graph with n vertices, the adjacency matrix A has entry aᵢⱼ = 1 when an edge connects vertex i to vertex j, or a weight when the graph is weighted. For an undirected graph, A is symmetric. The degree matrix D is diagonal, with dᵢᵢ equal to the degree of vertex i. The graph Laplacian is

Laplacians are used in connectivity analysis, spectral clustering, diffusion processes, and ranking. The number of zero eigenvalues of L equals the number of connected components for an undirected graph.

Machine learning

A dataset with m observations and n features is often stored as X ∈ ℝᵐˣⁿ. Linear regression predicts y using

where β is a parameter vector. Least squares minimizes ‖Xβ − y‖₂². Regularization can improve generalization and stability. Ridge regression uses

where α ≥ 0 controls the penalty. For α > 0 and suitable dimensions, the solution is

although software should solve the associated system rather than explicitly form the inverse.

9. Principal Component Analysis and Dimensionality Reduction

Principal component analysis (PCA) transforms correlated variables into orthogonal directions ordered by explained variance. Given centered data matrix X, the sample covariance matrix is

where m > 1 is the number of observations. The eigenvectors of C are principal directions, and their eigenvalues are the corresponding variances. Equivalently, PCA can be computed using the SVD X = UΣVᵀ; the columns of V are principal directions.

If Vₖ contains the first k principal directions, the reduced representation is

and the reconstruction is approximately

provided X has been centered. PCA can reduce storage, accelerate learning, visualize high-dimensional data, and suppress some noise. It is not automatically a feature-selection method: each component may combine many original variables, and high variance is not necessarily the same as high predictive value.

10. Numerical Computation and Conditioning

Exact algebra and floating-point computation are not identical. Computers represent most real numbers approximately, so rounding errors can accumulate. A problem is ill-conditioned when small input changes can cause large output changes. An algorithm is unstable when it introduces unnecessarily large errors even for a well-conditioned problem.

The condition number of an invertible matrix in a chosen norm is

It is always at least 1. A large condition number indicates sensitivity, not necessarily a poor algorithm. Practical best practices include:

• check dimensions before multiplication;
• scale features when appropriate;
• use pivoting in elimination;
• prefer QR or SVD when stability matters;
• avoid explicit matrix inversion for solving systems;
• exploit sparsity for large matrices;
• report tolerances when deciding whether a value is numerically zero;
• validate solutions by examining the residual r = b − Ax.

For sparse graphs and scientific systems, dense storage may be infeasible. Sparse formats store only nonzero entries and support matrix–vector multiplication without materializing all zeros.

11. Applied Case: PCA for Image Compression

Background

Consider an illustrative image-processing service that stores thousands of grayscale face images. Each image has 64 × 64 pixels and is represented as a vector in ℝ⁴⁰⁹⁶. Storing every image in full dimension requires substantial memory and makes similarity search expensive.

Problem

The service needs a lower-dimensional representation that preserves major visual patterns while reducing storage and computation. It must also avoid interpreting compressed components as automatically meaningful human attributes.

Analysis

Let X be the m × 4096 matrix whose rows are centered image vectors. Computing the SVD,

reveals directions of greatest variation. Suppose the first 100 singular directions preserve 92% of the total variance. The compressed representation is

where Z has 100 columns instead of 4096.

A common variance-retention measure is

where σᵢ are singular values. This ratio is valid for centered data when variance is assessed through the SVD; the common factor associated with sample covariance cancels in the ratio.

Approach and solution

The pipeline centers each pixel feature, computes a truncated SVD, stores Z and the retained basis V₁₀₀, and reconstructs an approximate image using X̂ = ZV₁₀₀ᵀ. Reconstruction quality is evaluated using a residual norm or image-specific measures. The number 100 is selected by balancing storage, visual quality, search accuracy, and latency.

Outcome

The representation reduces the feature dimension by more than 97% while retaining dominant global patterns. However, compression may remove small but important details, and the selected components may reflect lighting, demographic imbalance, or acquisition conditions rather than identity-relevant structure.

Learning points

• SVD provides both a computational method and an interpretable geometric model.
• Variance retention is a design criterion, not proof of task performance.
• Data preprocessing, centering, scaling, and validation affect the result.
• A mathematically effective representation can still create social or ethical risks if used in surveillance or automated decision-making without governance.

12. Limitations, Ethics, and Contemporary Practice

Linear models often provide transparency and efficient computation, but they may fail when relationships are nonlinear, data are poorly measured, or assumptions are violated. PCA and low-rank methods can amplify dominant patterns while suppressing minority or rare cases. In network analysis, a centrality score can affect resource allocation, yet the graph itself may encode historical bias.

Responsible practice requires documenting data sources, transformations, missing-value handling, scaling choices, and model limitations. Sensitive applications should assess privacy, fairness, security, and the consequences of false positives and false negatives. Matrix methods do not remove responsibility: they formalize assumptions and can make biased decisions appear objective.

Contemporary numerical linear algebra increasingly uses GPUs, distributed computation, randomized SVD, automatic differentiation, and specialized sparse solvers. These tools improve scale and speed, but they do not eliminate the need for dimension checks, conditioning analysis, reproducibility, and independent validation.

Chapter Summary

Linear algebra provides the structures and algorithms used to represent and transform computational data. Vectors describe points, features, and states; matrices represent datasets, transformations, systems, and networks. Matrix multiplication composes transformations, while rank, nullity, span, basis, and dimension describe the information preserved by a matrix.

Linear systems are solved through elimination and factorization, with rank determining consistency and uniqueness. Inner products, norms, orthogonality, and projections support least squares and geometric interpretation. Eigenvalues describe invariant directions and dynamics, while LU, QR, and SVD provide practical computational decompositions. SVD and eigenanalysis support PCA and dimensionality reduction. Applications include graphics, graph analytics, regression, image compression, and machine learning.

Reliable practice requires attention to dimensions, numerical conditioning, floating-point error, sparsity, validation, and ethical consequences. The most useful linear algebra is not merely symbolic manipulation; it is the disciplined interpretation of mathematical structure in a computational context.

Key Terms

Vector: An ordered collection of numbers representing a coordinate, feature, or state.

Matrix: A rectangular array of numbers used to represent data or a transformation.

Linear transformation: A function preserving vector addition and scalar multiplication.

Transpose: The matrix formed by exchanging rows and columns.

Inverse: A matrix that reverses the action of a square nonsingular matrix.

Rank: The dimension of a matrix’s column space, equal to its number of pivots.

Null space: The set of vectors mapped to zero by a matrix.

Span: The set of all linear combinations of a collection of vectors.

Basis: A linearly independent spanning set.

Dimension: The number of vectors in a basis of a finite-dimensional space.

Inner product: A scalar product such as xᵀy that measures alignment.

Norm: A function measuring vector magnitude or length.

Orthogonality: The condition xᵀy = 0.

Eigenvalue: A scalar λ satisfying Av = λv for a nonzero vector v.

Eigenvector: A nonzero vector whose direction is preserved by a matrix.

LU factorization: A decomposition involving lower- and upper-triangular matrices.

QR factorization: A decomposition into an orthonormal factor and an upper-triangular factor.

Singular value decomposition: A factorization A = UΣVᵀ using orthogonal factors and nonnegative singular values.

Condition number: A measure of sensitivity of a computational problem to input perturbations.

Principal component analysis: A method that represents centered data along ordered orthogonal variance directions.

Review Questions

Short Answer Questions

1. What dimension must a vector x have for the product Ax to be defined when A is m × n?
2. Define linear independence and explain its relationship to a basis.
3. What does the rank–nullity theorem state?
4. Why is QR factorization useful for least-squares problems?
5. What geometric information is represented by an eigenvector?

Long Answer Questions

1. Explain Gaussian elimination, including the elementary row operations and the role of pivoting.
2. Compare LU, QR, and SVD in terms of structure, applications, and numerical reliability.
3. Derive the projection of a vector onto a nonzero vector and explain the orthogonality of the residual.
4. Explain PCA using both covariance eigenvectors and the SVD of a centered data matrix.
5. Discuss how matrices are used in computer graphics and network analysis, including at least one limitation in each application.

Analytical / Application Questions

1. A dataset contains 500 observations and 20 features. Explain how you would preprocess it and use PCA to create a 5-dimensional representation. State what information may be lost.
2. A graph Laplacian has three zero eigenvalues. Under the standard undirected-graph Laplacian definition, what can be concluded about the graph, and what assumptions are required?
3. A linear system has a very large condition number but a small residual after solution. Explain why the solution may still be unreliable and propose two diagnostic or mitigation strategies.

Multiple Choice Questions with Answers

Question 1

If A is an m × n matrix and x is a vector, what must be the dimension of x for Ax to be defined?

A. m

B. n

C. m + n

D. m − n

Correct Answer: B. n

Question 2

Which condition guarantees that two vectors x and y are orthogonal?

A. xᵀy = 1

B. ‖x‖₂ = ‖y‖₂

C. xᵀy = 0

D. x = y

Correct Answer: C. xᵀy = 0

Question 3

For a consistent system Ax = b with n unknowns, which condition gives a unique solution?

A. rank(A) = 0

B. rank(A) < n

C. rank(A) = n

D. rank(A) > n

Correct Answer: C. rank(A) = n

Question 4

What is the projection of b onto a nonzero vector a?

A. (aᵀa)/(aᵀb) · b

B. (aᵀb)/(aᵀa) · a

C. (bᵀb)/(aᵀa) · b

D. aᵀb · a

Correct Answer: B. (aᵀb)/(aᵀa) · a

Question 5

Which equation defines an eigenvector v with eigenvalue λ?

A. Av = v + λ

B. Av = λv

C. A + v = λv

D. Aᵀv = 0 for every v

Correct Answer: B. Av = λv

Question 6

For an undirected graph, the standard graph Laplacian is defined as

A. L = A − D

B. L = AᵀA

C. L = D − A

D. L = D + A⁻¹

Correct Answer: C. L = D − A

Question 7

Which factorization is especially associated with best low-rank approximation?

A. SVD

B. LU only

C. Cholesky only

D. Diagonal scaling only

Correct Answer: A. SVD

Question 8

If a = [1, 2]ᵀ and b = [3, 1]ᵀ, what is projₐ(b)?

A. [1, 2]ᵀ

B. [2, −1]ᵀ

C. [3, 1]ᵀ

D. [5, 5]ᵀ

Correct Answer: A. [1, 2]ᵀ

Question 9

In PCA, the principal directions of a centered dataset are commonly obtained from

A. the eigenvectors of its covariance matrix

B. the row sums only

C. the determinant alone

D. the diagonal entries of the original data matrix

Correct Answer: A. the eigenvectors of its covariance matrix

Question 10

What does a large condition number generally indicate?

A. The problem is insensitive to perturbations

B. The matrix must be sparse

C. Small input changes may cause large output changes

D. The matrix has no eigenvalues

Correct Answer: C. Small input changes may cause large output changes