Unit 3: Linear Algebra

I. Foundations and Conventions

Linear algebra studies vectors, matrices, linear transformations, and systems governed by linear relations. Its central principle is linearity: addition and scalar multiplication are preserved, allowing complicated multidimensional problems to be represented and solved systematically.

• Scalars: Numbers such as (2), (-3), or (1/2), usually taken from the real field (\mathbb{R}) or complex field (\mathbb{C}).
• Vectors: Ordered lists of scalars, commonly written as column vectors in (\mathbb{R}^n).
• Linear combination: An expression (c_1v_1+\cdots+c_kv_k), where (v_i) are vectors and (c_i) are scalars.
• Linear independence: Vectors (v_1,\ldots,v_k) are independent when
  
  TEXT

    c₁v₁ + c₂v₂ + ··· + cₖvₖ = 0

  
  implies (c_1=c_2=\cdots=c_k=0).
• Span: The set of all linear combinations of a collection of vectors.
• Basis and dimension: A basis is a linearly independent spanning set; its number of vectors is the dimension.
• Index convention: In a matrix (A=[a_{ij}]), (i) identifies the row and (j) identifies the column.
• Zero and identity objects: (0) denotes a zero scalar, vector, or matrix as context requires; (I_n) denotes the (n\times n) identity matrix.

II. Matrices — Representation and Operations

A. matrices

A matrix is a rectangular array of scalars used to represent data, coefficients, or a linear transformation.

• Order: A matrix with (m) rows and (n) columns has order (m\times n):
  
  TEXT

    A = [aᵢⱼ],  1 ≤ i ≤ m,  1 ≤ j ≤ n

  
  Here, (a_{ij}) is the entry in row (i), column (j).
• Important types:
  • Row and column matrices: Orders (1\times n) and (m\times1), respectively.
  • Square matrix: Has equal row and column counts, (n\times n).
  • Diagonal matrix: Satisfies (a_{ij}=0) whenever (i\ne j).
  • Identity matrix: Has (1) on its main diagonal and (0) elsewhere.
  • Symmetric matrix: Satisfies (A^T=A), where (A^T) is the transpose.
  • Triangular matrix: Has zeros either below or above the main diagonal.
• Equality and addition: Matrices (A) and (B) are equal when they have the same order and (a{ij}=b{ij}). For equal-sized matrices,
  
  TEXT

    (A + B)ᵢⱼ = aᵢⱼ + bᵢⱼ

• Scalar multiplication: For scalar (c), ((cA){ij}=ca{ij}).
• Matrix multiplication: If (A) is (m\times n) and (B) is (n\times p), then (AB) is (m\times p):
  
  TEXT

    (AB)ᵢⱼ = Σₖ₌₁ⁿ aᵢₖbₖⱼ

  
  Matrix multiplication is associative and distributive but generally not commutative: (AB\ne BA).
• Transpose rules: ((A^T)^T=A), ((A+B)^T=A^T+B^T), and ((AB)^T=B^TA^T).
• Inverse: A square matrix (A) is invertible if a matrix (A^{-1}) exists such that
  
  TEXT

    AA⁻¹ = A⁻¹A = I

• Worked example: For
  
  TEXT

    A = [1  2]    B = [ 2  0]
        [3  4]        [-1  5]

  
  multiplication gives
  
  TEXT

    AB = [1(2)+2(-1)   1(0)+2(5)] = [0  10]
         [3(2)+4(-1)   3(0)+4(5)]   [2  20]

B. Rank and Applications

Rank measures the number of linearly independent rows or columns and controls many matrix-based conclusions.

• Rank: (\operatorname{rank}(A)) equals the number of pivots in a row-echelon form of (A).
• Full rank: An (m\times n) matrix has full rank when its rank is (\min(m,n)).
• Transformation viewpoint: Multiplication (x\mapsto Ax) maps vectors from (\mathbb{R}^n) to (\mathbb{R}^m).
• Applications: Matrices encode graphs, recurrences, geometric transformations, statistical data, and coefficients of linear systems.

III. Determinants — Invertibility and Scaling

A. determinants

The determinant is a scalar assigned to a square matrix that indicates invertibility and the signed scaling of area or volume.

• Second-order formula: For
  
  TEXT

    A = [a  b]
        [c  d]

  
  the determinant is (\det(A)=ad-bc).
• Cofactor expansion: For an (n\times n) matrix,
  
  TEXT

    det(A) = Σⱼ₌₁ⁿ aᵢⱼCᵢⱼ
    Cᵢⱼ = (-1)ⁱ⁺ʲMᵢⱼ

  
  Here, (M{ij}) is the minor obtained by deleting row (i) and column (j), and (C{ij}) is its cofactor.
• Triangular case: The determinant of a triangular matrix is the product of its diagonal entries.
• Row-operation effects:
  • Interchanging two rows changes the determinant’s sign.
  • Multiplying one row by (c) multiplies the determinant by (c).
  • Adding a multiple of one row to another leaves the determinant unchanged.
• Core identities: (\det(AB)=\det(A)\det(B)), (\det(A^T)=\det(A)), and (\det(I)=1).
• Invertibility criterion: A square matrix is invertible exactly when (\det(A)\ne0).
• Worked example:
  
  TEXT

    A = [2  1  0]
        [0  3  4]
        [0  0  5]

  
  Since (A) is upper triangular, (\det(A)=2\cdot3\cdot5=30).

B. Geometric and Algebraic Significance

The determinant connects algebraic solvability with geometric change under a linear transformation.

• Geometric scale: The absolute value (|\det(A)|) is the factor by which (A) scales area or volume.
• Orientation: A negative determinant reverses orientation; a positive determinant preserves it.
• Singularity: If (\det(A)=0), the transformation collapses at least one dimension, so its columns are linearly dependent.
• Computational limitation: Direct cofactor expansion becomes expensive for large matrices; elimination-based methods are more efficient.

IV. Systems of Linear Equations — Consistency and Solution

A. system of linear equations

A system of linear equations is a collection of equations that can be represented compactly as (Ax=b).

• Matrix form:
  
  TEXT

    Ax = b

  
  Here, (A) is the coefficient matrix, (x) is the vector of unknowns, and (b) is the constants vector.
• Augmented matrix: The notation ([A\mid b]) combines coefficients and constants for row reduction.
• Elementary row operations: Swap two rows, multiply a row by a nonzero scalar, or add a multiple of one row to another.
• Gaussian elimination: Converts ([A\mid b]) into row-echelon form, followed by back-substitution.
• Gauss–Jordan elimination: Continues to reduced row-echelon form, where every pivot is (1) and is the only nonzero entry in its column.
• Consistency criterion: A system is consistent precisely when
  
  TEXT

    rank(A) = rank([A | b])

• Solution counts:
  • Unique solution: The system is consistent and every variable column contains a pivot.
  • Infinitely many solutions: The system is consistent and has at least one free variable.
  • No solution: Reduction produces a row such as ([0\ 0\mid c]), where (c\ne0).
• Worked example:
  
  TEXT

    x + y = 5
    2x - y = 1

  
  Adding the equations gives (3x=6), so (x=2), and substitution gives (y=3).

B. Homogeneous Systems and Interpretation

A homogeneous system has the form (Ax=0) and is always consistent because (x=0) is a solution.

• Trivial solution: (x=0) satisfies every homogeneous system.
• Nontrivial solutions: They exist when (A) has fewer pivots than variables; for square (A), this is equivalent to (\det(A)=0).
• Null space: The solution set ({x:Ax=0}) is the null space of (A).
• Dimension relation:
  
  TEXT

    rank(A) + nullity(A) = n

  
  Here, (n) is the number of columns and nullity is the dimension of the null space.

V. Eigenvalues — Invariant Scaling Factors

A. eigenvalues

An eigenvalue of a square matrix (A) is a scalar (\lambda) for which (Av=\lambda v) holds for some nonzero vector (v).

• Characteristic equation:
  
  TEXT

    det(A - λI) = 0

  
  Here, (I) is the identity matrix and (\lambda) is the unknown eigenvalue.
• Characteristic polynomial: The polynomial (p(\lambda)=\det(A-\lambda I)) has degree (n) for an (n\times n) matrix.
• Multiplicity: Algebraic multiplicity is the number of times an eigenvalue occurs as a root of (p(\lambda)).
• Triangular matrices: Their eigenvalues are exactly their diagonal entries.
• Trace and determinant:
  
  TEXT

    Σᵢ λᵢ = tr(A),    ∏ᵢ λᵢ = det(A)

  
  The eigenvalues (\lambda_i) are counted with algebraic multiplicity, and (\operatorname{tr}(A)) is the sum of diagonal entries.
• Worked example: For
  
  TEXT

    A = [2  1]
        [0  3]

  
  the characteristic equation is ((2-\lambda)(3-\lambda)=0), giving eigenvalues (2) and (3).

B. Significance and Limitations

Eigenvalues describe intrinsic behavior that remains visible under a change of basis.

• Invertibility: A matrix is invertible exactly when (0) is not an eigenvalue.
• Powers and dynamics: Eigenvalues help determine long-term behavior of (A^kx), recurrences, and discrete dynamical systems.
• Similarity: Similar matrices (A) and (P^{-1}AP) have the same eigenvalues.
• Limitation: Real matrices can possess complex eigenvalues, and repeated eigenvalues need not provide enough independent eigenvectors for diagonalization.

VI. Eigenvectors — Invariant Directions

A. eigenvectors

An eigenvector is a nonzero vector whose direction is unchanged by a linear transformation, although its magnitude or orientation may change.

• Computation: For each eigenvalue (\lambda), solve
  
  TEXT

    (A - λI)v = 0,    v ≠ 0

  
  The solution set is the eigenspace (E_\lambda=\ker(A-\lambda I)).
• Geometric multiplicity: The dimension of (E_\lambda); it is at least (1) and no greater than the algebraic multiplicity.
• Scaling: If (v) is an eigenvector, then every nonzero multiple (cv) is also an eigenvector for the same eigenvalue.
• Independence: Eigenvectors associated with distinct eigenvalues are linearly independent.
• Worked example: For
  
  TEXT

    A = [2  1]
        [0  3]

  
  when (\lambda=2), solving ((A-2I)v=0) gives (v=(1,0)^T). When (\lambda=3), it gives vectors proportional to ((1,1)^T).

B. Diagonalization and Applications

Eigenvectors provide a coordinate system in which some linear transformations become diagonal.

• Diagonalization: If (A) has (n) linearly independent eigenvectors, then
  
  TEXT

    A = PDP⁻¹

  
  Here, the columns of (P) are eigenvectors and (D) contains corresponding eigenvalues on its diagonal.
• Matrix powers: Diagonalization gives (A^k=PD^kP^{-1}), where (D^k) is found by raising each diagonal entry to (k).
• Symmetric matrices: Every real symmetric matrix has real eigenvalues and an orthonormal basis of eigenvectors.
• Applications: Eigenvectors appear in stability analysis, graph theory, Markov chains, principal component analysis, and recurrence relations.

VII. LU Decomposition — Structured Elimination

A. LU decomposition

LU decomposition factors a square matrix into a lower triangular matrix (L) and an upper triangular matrix (U), converting elimination into reusable matrix operations.

• Factorization:
  
  TEXT

    A = LU

  
  Here, (L) is lower triangular, commonly with diagonal entries (1), and (U) is upper triangular.
• Elimination principle: Multipliers used to eliminate entries below the pivots of (A) become entries of (L); the resulting echelon matrix is (U).
• Solving a system: If (Ax=b) and (A=LU), solve in two stages:
  1. Forward substitution solves (Ly=b).
  2. Back-substitution solves (Ux=y).
• Worked example:
  
  TEXT

    A = [2  1] = [1  0][2  1]
        [4  3]   [2  1][0  1]

  
  Thus,
  
  TEXT

    L = [1  0],    U = [2  1]
        [2  1]         [0  1]

  
  The multiplier (4/2=2) appears below the diagonal in (L).

B. Pivoting, Uses, and Limitations

Practical LU algorithms use pivoting to avoid zero or numerically unstable pivots.

• Pivoted form:
  
  TEXT

    PA = LU

  
  Here, (P) is a permutation matrix recording row exchanges.
• Existence: An LU factorization without row exchanges is available when the required elimination pivots are nonzero; pivoting handles many cases where this condition fails.
• Efficiency: Once (A=LU) is computed, multiple systems (Ax=b_i) with different right-hand sides require only forward and backward substitution.
• Determinant: When (L) has unit diagonal, (\det(A)=\det(U)), adjusted by the sign of row permutations when (P) is used.
• Limitations: Singular matrices may prevent a usable factorization, while poorly scaled matrices can require pivoting for numerical reliability.