Engineering Mathematics: Linear Algebra

Syllabus: Matrices, determinants, System of linear equations, Eigenvalues and eigenvectors, LU decomposition.

Mark Distribution in Previous GATE

Welcome to the "Engineering Mathematics: Linear Algebra" chapter of your GATE Computer Science preparation. This section serves as a comprehensive, exam-focused reference to help you master the fundamental concepts and problem-solving techniques essential for success.

Subject Overview

Linear Algebra is the branch of mathematics concerning vector spaces and linear mappings between such spaces. It is a cornerstone of modern computing, underpinning areas like machine learning (e.g., PCA, SVMs, neural networks), computer graphics, data science, algorithm design, and optimization. For GATE CS, Linear Algebra typically contributes a significant portion of the Engineering Mathematics section, often carrying 3-5 marks out of the total 8-10 marks allocated to mathematics. Questions can range from direct computational problems (e.g., finding determinants, eigenvalues, ranks) to conceptual understanding (e.g., properties of vector spaces, subspaces, consistency of systems of equations) and application-based scenarios. Proficiency in this subject is not just about scoring marks but also about building a strong mathematical foundation for advanced computer science topics.

Topic-wise Key Concepts

Cartesian Coordinates

Cartesian coordinates provide a way to uniquely specify the position of a point in a space using numerical values. In 2D, a point is defined by its distance from two perpendicular axes ($x, y$), and in 3D, by its distance from three mutually perpendicular axes ($x, y, z$).

• Definition: A system that uses an ordered set of numbers (coordinates) to specify the location of a point in a space. For a 2D plane, it's $(x, y)$; for 3D space, it's $(x, y, z)$.

• Distance Formula (2D): The distance between two points $P_1(x_1, y_1)$ and $P_2(x_2, y_2)$ is given by:

$d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$

• Distance Formula (3D): The distance between two points $P_1(x_1, y_1, z_1)$ and $P_2(x_2, y_2, z_2)$ is given by:

$d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2 + (z_2 - z_1)^2}$

• Midpoint Formula (2D): The midpoint $M$ of a line segment connecting $P_1(x_1, y_1)$ and $P_2(x_2, y_2)$ is:

$M = \left( \frac{x_1 + x_2}{2}, \frac{y_1 + y_2}{2} \right)$

Properties:

• Allows geometric problems to be translated into algebraic ones.

• Forms the basis for vector representation and operations.

Common Pitfalls:

• Confusing x and y coordinates, especially when dealing with transformations.

• Incorrectly applying distance or midpoint formulas.

Problem-Solving Techniques:

• Visualize the points and vectors in the coordinate system.

• Break down complex geometric problems into simpler algebraic calculations.

Determinant

The determinant is a scalar value that can be computed from the elements of a square matrix. It provides crucial information about the matrix, such as its invertibility and the volume scaling factor of the linear transformation it represents.

• Definition: A scalar value associated with a square matrix $A$, denoted as $\det(A)$ or $|A|$.

Formulas:

• 1. For a $2 \times 2$ matrix: If $A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}$, then $|A| = ad - bc$.
• 2. For a $3 \times 3$ matrix (Sarrus' Rule): If $A = \begin{pmatrix} a & b & c \\ d & e & f \\ g & h & i \end{pmatrix}$, then

$|A| = a(ei - fh) - b(di - fg) + c(dh - eg)$. This can also be written as $a \begin{vmatrix} e & f \\ h & i \end{vmatrix} - b \begin{vmatrix} d & f \\ g & i \end{vmatrix} + c \begin{vmatrix} d & e \\ g & h \end{vmatrix}$.

• 3. General $n \times n$ matrix (Laplace Expansion/Cofactor Expansion): $|A| = \sum_{j=1}^n (-1)^{i+j} a_{ij} M_{ij}$ (along row $i$) or $|A| = \sum_{i=1}^n (-1)^{i+j} a_{ij} M_{ij}$ (along column $j$) where $M_{ij}$ is the minor (determinant of the submatrix obtained by deleting row $i$ and column $j$).

Properties:

• $\det(A^T) = \det(A)$

• $\det(AB) = \det(A) \det(B)$

• $\det(kA) = k^n \det(A)$ for an $n \times n$ matrix $A$ and scalar $k$.

• If a matrix has a row or column of zeros, its determinant is 0.

• If a matrix has two identical rows or columns, its determinant is 0.

• If a matrix is triangular (upper or lower), its determinant is the product of its diagonal elements.

• Swapping two rows/columns changes the sign of the determinant.

• Adding a multiple of one row/column to another row/column does not change the determinant.

• A square matrix $A$ is invertible if and only if $\det(A) \neq 0$.

• $\det(A^{-1}) = \frac{1}{\det(A)}$

Common Pitfalls:

• Sign errors in cofactor expansion.

• Incorrectly applying properties, especially for scalar multiplication $\det(kA)$.

• Assuming $\det(A + B) = \det(A) + \det(B)$ (which is generally false).

Problem-Solving Techniques:

• For larger matrices, use row/column operations to create zeros and simplify the calculation before applying cofactor expansion (e.g., make it triangular).

• Exploit properties (e.g., identical rows/columns, triangular form) to quickly find the determinant.

• Choose the row or column with the most zeros for cofactor expansion.

Eigen Value

Eigenvalues are special scalar values associated with a square matrix that characterize its fundamental properties. When a linear transformation is applied to an eigenvector, the eigenvector's direction remains unchanged, only its magnitude is scaled by the corresponding eigenvalue.

• Definition: For a square matrix $A$, a scalar $\lambda$ is an eigenvalue if there exists a non-zero vector $\mathbf{v}$ (eigenvector) such that $A\mathbf{v} = \lambda\mathbf{v}$.

Formulas/Theorems:

• 1. Characteristic Equation: To find eigenvalues, solve the equation $\det(A - \lambda I) = 0$, where $I$ is the identity matrix of the same dimension as $A$.
• 2. Cayley-Hamilton Theorem: Every square matrix satisfies its own characteristic equation. If $P(\lambda) = \det(A - \lambda I)$ is the characteristic polynomial, then $P(A) = 0$. This is useful for finding powers of a matrix or its inverse.
• 3. Sum of Eigenvalues: The sum of the eigenvalues of a matrix $A$ is equal to its trace (sum of diagonal elements): $\sum \lambda_i = \text{trace}(A)$.
• 4. Product of Eigenvalues: The product of the eigenvalues of a matrix $A$ is equal to its determinant: $\prod \lambda_i = \det(A)$.

Properties:

• If $\lambda$ is an eigenvalue of $A$, then $\lambda^k$ is an eigenvalue of $A^k$.

• If $\lambda$ is an eigenvalue of $A$, then $1/\lambda$ is an eigenvalue of $A^{-1}$ (if $A$ is invertible).

• If $\lambda$ is an eigenvalue of $A$, then $k\lambda$ is an eigenvalue of $kA$.

• The eigenvalues of a symmetric matrix are always real.

• Eigenvectors corresponding to distinct eigenvalues are linearly independent.

• For a real symmetric matrix, eigenvectors corresponding to distinct eigenvalues are orthogonal.

• The eigenvalues of a triangular matrix (upper or lower) are its diagonal entries.

• A matrix $A$ is singular (non-invertible) if and only if 0 is an eigenvalue of $A$.

Common Pitfalls:

• Algebraic errors when solving the characteristic equation.

• Forgetting to check for non-zero eigenvectors.

• Confusing algebraic and geometric multiplicity.

Problem-Solving Techniques:

• Always start by setting up the characteristic equation $\det(A - \lambda I) = 0$.

• For $2 \times 2$ matrices, use $\lambda^2 - \text{trace}(A)\lambda + \det(A) = 0$.

• Use the sum and product of eigenvalues properties to verify your calculated eigenvalues or to find a missing eigenvalue.

• For eigenvectors, substitute each eigenvalue back into $(A - \lambda I)\mathbf{v} = \mathbf{0}$ and solve the resulting system of equations.

Gaussian Elimination

Gaussian elimination is an algorithm used to solve systems of linear equations, find the rank of a matrix, compute the inverse of a matrix, and calculate determinants. It transforms a matrix into row echelon form using elementary row operations.

• Definition: A systematic procedure to transform a matrix into row echelon form (or reduced row echelon form) using elementary row operations.

Elementary Row Operations:

• 1. Swapping two rows ($R_i \leftrightarrow R_j$).
• 2. Multiplying a row by a non-zero scalar ($kR_i \rightarrow R_i$).
• 3. Adding a multiple of one row to another row ($R_i + kR_j \rightarrow R_i$).

Row Echelon Form (REF): A matrix is in REF if:

• All non-zero rows are above any rows of all zeros.

• The leading entry (pivot) of each non-zero row is in a column to the right of the leading entry of the row above it.

• All entries in a column below a leading entry are zeros.

Reduced Row Echelon Form (RREF): A matrix is in RREF if it is in REF and:

• The leading entry in each non-zero row is 1 (called a leading 1).

• Each column containing a leading 1 has zeros everywhere else.

Applications:

• Solving systems of linear equations.

• Finding the rank of a matrix.

• Computing the inverse of a matrix (by augmenting $[A|I]$ and reducing to $[I|A^{-1}]$).

• Calculating determinants (by keeping track of row operations).

Common Pitfalls:

• Arithmetic errors during row operations.

• Forgetting to apply operations to the augmented part of the matrix when solving systems or finding inverses.

• Incorrectly identifying pivot elements.

Problem-Solving Techniques:

• Always aim to create zeros below the pivot elements first.

• Work column by column from left to right.

• Use fractions carefully; sometimes it's better to multiply a row to avoid fractions temporarily.

• For solving systems, use back-substitution after reaching REF.

LU Decomposition

LU decomposition factors a square matrix $A$ into the product of a lower triangular matrix $L$ and an upper triangular matrix $U$. This factorization is particularly useful for efficiently solving multiple systems of linear equations with the same coefficient matrix, as it simplifies the process into two triangular systems.

• Definition: A factorization of a square matrix $A$ into the product of a lower triangular matrix $L$ (with 1s on the diagonal) and an upper triangular matrix $U$, such that $A = LU$.

Process:

• 1. Use Gaussian elimination to transform $A$ into an upper triangular matrix $U$.
• 2. The lower triangular matrix $L$ is constructed using the multipliers used in the Gaussian elimination process. If $R_i - kR_j \rightarrow R_i$ was used, then $L_{ij} = k$. The diagonal elements of $L$ are 1s.
• 3. If row swaps are needed, a permutation matrix $P$ is introduced, such that $PA = LU$.

• Solving $A\mathbf{x} = \mathbf{b}$ using LU Decomposition:

• 1. Substitute $A = LU$: $LU\mathbf{x} = \mathbf{b}$.
• 2. Let $U\mathbf{x} = \mathbf{y}$.
• 3. Solve $L\mathbf{y} = \mathbf{b}$ for $\mathbf{y}$ using forward substitution (since $L$ is lower triangular).
• 4. Solve $U\mathbf{x} = \mathbf{y}$ for $\mathbf{x}$ using backward substitution (since $U$ is upper triangular).

Properties:

• Not all matrices have an LU decomposition without pivoting (row swaps).

• If $A$ is non-singular and all its leading principal minors are non-zero, then $A$ has a unique LU decomposition.

Common Pitfalls:

• Incorrectly forming $L$ from the multipliers.

• Errors in forward or backward substitution.

• Forgetting the permutation matrix $P$ if row swaps are involved.

Problem-Solving Techniques:

• Carefully track the multipliers used in Gaussian elimination to construct $L$.

• Practice forward and backward substitution for efficiency.

• Recognize when pivoting is necessary (e.g., if a pivot element becomes zero).

Matrix

A matrix is a rectangular array of numbers, symbols, or expressions arranged in rows and columns. Matrices are fundamental to linear algebra, representing linear transformations, systems of equations, and data structures.

• Definition: A rectangular array of numbers (or functions) arranged in $m$ rows and $n$ columns. Denoted as $A_{m \times n}$.

Types of Matrices:

• Square Matrix: $m = n$.

• Row Matrix: $m = 1$.

• Column Matrix (Vector): $n = 1$.

• Identity Matrix ($I$): Square matrix with 1s on the main diagonal and 0s elsewhere. $AI = IA = A$.

• Zero Matrix ($0$): All elements are 0. $A + 0 = A$.

• Diagonal Matrix: Square matrix where all non-diagonal elements are 0.

• Scalar Matrix: A diagonal matrix where all diagonal elements are equal.

• Symmetric Matrix: $A = A^T$.

• Skew-Symmetric Matrix: $A = -A^T$. Diagonal elements are 0.

• Orthogonal Matrix: $AA^T = A^T A = I$, which implies $A^{-1} = A^T$. Determinant is $\pm 1$.

• Invertible/Non-singular Matrix: A square matrix $A$ for which there exists a matrix $A^{-1}$ such that $AA^{-1} = A^{-1}A = I$. $\det(A) \neq 0$.

• Singular Matrix: A square matrix $A$ for which $\det(A) = 0$. It does not have an inverse.

Operations:

• 1. Addition/Subtraction: Element-wise, only for matrices of the same dimensions. $(A + B)_{ij} = A_{ij} + B_{ij}$.
• 2. Scalar Multiplication: Multiply each element by the scalar. $(kA)_{ij} = kA_{ij}$.
• 3. Matrix Multiplication: $(AB)_{ij} = \sum_{k=1}^p A_{ik}B_{kj}$. Requires number of columns of $A$ to equal number of rows of $B$. Resulting matrix has dimensions $m \times q$ if $A$ is $m \times p$ and $B$ is $p \times q$.
• 4. Transpose ($A^T$): Rows become columns and columns become rows. $(A^T)_{ij} = A_{ji}$.
• 5. Inverse ($A^{-1}$): For a $2 \times 2$ matrix $A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}$, $A^{-1} = \frac{1}{ad-bc} \begin{pmatrix} d & -b \\ -c & a \end{pmatrix}$. For general $n \times n$, $A^{-1} = \frac{1}{\det(A)} \text{adj}(A)$, where $\text{adj}(A)$ is the adjugate matrix (transpose of the cofactor matrix).

Properties:

• Matrix addition is commutative: $A + B = B + A$.

• Matrix multiplication is associative: $(AB)C = A(BC)$.

• Matrix multiplication is generally NOT commutative: $AB \neq BA$.

• $(A + B)^T = A^T + B^T$.

• $(AB)^T = B^T A^T$.

• $(A^{-1})^{-1} = A$.

• $(AB)^{-1} = B^{-1} A^{-1}$.

• $(A^T)^{-1} = (A^{-1})^T$.

Common Pitfalls:

• Incorrect dimensions for addition or multiplication.

• Assuming commutativity for matrix multiplication.

• Errors in calculating inverses, especially for larger matrices.

Problem-Solving Techniques:

• Always check dimensions before performing operations.

• For matrix multiplication, visualize the dot products of rows and columns.

• For inverses, use the adjugate formula for $2 \times 2$ and Gaussian elimination for larger matrices.

Multiplicity

Multiplicity refers to how many times an eigenvalue appears as a root of the characteristic polynomial (algebraic multiplicity) and the dimension of its corresponding eigenspace (geometric multiplicity). These concepts are crucial for understanding diagonalizability of a matrix.

Definition:

• Algebraic Multiplicity (AM): The number of times an eigenvalue $\lambda$ appears as a root of the characteristic polynomial $\det(A - \lambda I) = 0$.

• Geometric Multiplicity (GM): The dimension of the eigenspace corresponding to $\lambda$, which is the number of linearly independent eigenvectors associated with $\lambda$. It is given by $n - \text{rank}(A - \lambda I)$, where $n$ is the dimension of the matrix.

Properties/Theorems:

• For any eigenvalue $\lambda$, $1 \leq \text{GM}(\lambda) \leq \text{AM}(\lambda)$.

• A matrix $A$ is diagonalizable if and only if for every eigenvalue $\lambda$, $\text{AM}(\lambda) = \text{GM}(\lambda)$.

• If all eigenvalues are distinct, then $\text{AM}(\lambda) = \text{GM}(\lambda) = 1$ for all $\lambda$, and the matrix is diagonalizable.

Common Pitfalls:

• Confusing AM and GM.

• Incorrectly calculating the rank of $(A - \lambda I)$.

• Assuming diagonalizability based only on AM without checking GM.

Problem-Solving Techniques:

• First, find all eigenvalues and their algebraic multiplicities by solving $\det(A - \lambda I) = 0$.

• For each eigenvalue, calculate the rank of $(A - \lambda I)$ to find its geometric multiplicity.

• Compare AM and GM for each eigenvalue to determine diagonalizability.

Orthonormality

Orthonormality describes a set of vectors that are mutually orthogonal (perpendicular) and each has a unit length (normalized). Orthonormal bases simplify many calculations in linear algebra, particularly in projections and coordinate transformations.

Definition:

• Orthogonal Vectors: Two vectors $\mathbf{u}$ and $\\$mathbf{v}$are orthogonal if their dot product is zero:$\mathbf{u} \cdot \mathbf{v} = \mathbf{u}^T \mathbf{v} = 0$.

• Normalized Vector: A vector $\mathbf{u}$ is normalized if its length (magnitude) is 1: $\|\mathbf{u}\| = \sqrt{\mathbf{u} \cdot \mathbf{u}} = 1$.

• Orthonormal Set: A set of vectors $\{\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_k\}$ is orthonormal if they are mutually orthogonal and each vector is normalized. That is, $\mathbf{v}_i \cdot \mathbf{v}_j = \delta_{ij}$ (Kronecker delta), where $\delta_{ij} = 1$ if $i = j$ and 0 if $i \neq j$.

• Gram-Schmidt Orthonormalization Process: A procedure to transform a set of linearly independent vectors $\{\mathbf{x}_1, \dots, \mathbf{x}_k\}$ into an orthonormal set $\{\mathbf{u}_1, \dots, \mathbf{u}_k\}$.

• 1. $\mathbf{v}_1 = \mathbf{x}_1$
• 2. $\mathbf{v}_2 = \mathbf{x}_2 - \text{proj}_{\mathbf{v}_1} \mathbf{x}_2 = \mathbf{x}_2 - \frac{\mathbf{x}_2 \cdot \mathbf{v}_1}{\|\mathbf{v}_1\|^2} \mathbf{v}_1$
• 3. $\mathbf{v}_3 = \mathbf{x}_3 - \text{proj}_{\mathbf{v}_1} \mathbf{x}_3 - \text{proj}_{\mathbf{v}_2} \mathbf{x}_3 = \mathbf{x}_3 - \frac{\mathbf{x}_3 \cdot \mathbf{v}_1}{\|\mathbf{v}_1\|^2} \mathbf{v}_1 - \frac{\mathbf{x}_3 \cdot \mathbf{v}_2}{\|\mathbf{v}_2\|^2} \mathbf{v}_2$
• 4. Continue for all vectors.
• 5. Normalize each $\mathbf{v}_i$: $\mathbf{u}_i = \frac{\mathbf{v}_i}{\|\mathbf{v}_i\|}$.

Properties:

• An orthonormal set of vectors is always linearly independent.

• If $Q$ is an orthogonal matrix (columns form an orthonormal set), then $Q^T Q = I$, and $Q^{-1} = Q^T$.

• For an orthogonal matrix $Q$, $\|Q\mathbf{x}\| = \|\mathbf{x}\|$ (preserves length).

• For an orthogonal matrix $Q$, $(Q\mathbf{x}) \cdot (Q\mathbf{y}) = \mathbf{x} \cdot \mathbf{y}$ (preserves dot product and angle).

Common Pitfalls:

• Arithmetic errors in Gram-Schmidt, especially with projections.
• Forgetting to normalize vectors after making them orthogonal.
• Confusing orthogonal with orthonormal.

Problem-Solving Techniques:

• Systematically apply the Gram-Schmidt process, calculating one orthogonal vector at a time.
• Double-check dot products to ensure orthogonality.
• Always normalize the final set of orthogonal vectors.

Rank of Matrix

The rank of a matrix is a fundamental property that measures the "linear independence" present in its rows and columns. It indicates the dimension of the vector space spanned by its rows or columns, and is crucial for understanding the solvability of linear systems.

• Definition: The maximum number of linearly independent row vectors (row rank) or column vectors (column rank) in a matrix. The row rank is always equal to the column rank.

Calculation Methods:

• 1. Using Row Echelon Form: The rank of a matrix is the number of non-zero rows in its row echelon form.
• 2. Using Determinants (Minors): The rank of a matrix $A$ is the largest integer $r$ such that there exists an $r \times r$ submatrix of $A$ with a non-zero determinant.

Properties/Theorems:

• For an $m \times n$ matrix $A$, $\text{rank}(A) \leq \min(m, n)$.
• $\text{rank}(A) = 0$ if and only if $A$ is a zero matrix.
• $\text{rank}(A) = \text{rank}(A^T)$.
• $\text{rank}(AB) \leq \min(\text{rank}(A), \text{rank}(B))$.
• Rank-Nullity Theorem: For an $m \times n$ matrix $A$, $\text{rank}(A) + \text{nullity}(A) = n$, where $\text{nullity}(A)$ is the dimension of the null space (kernel) of $A$.
• A square matrix $A$ of size $n \times n$ is invertible if and only if $\text{rank}(A) = n$.
• For a system $\mathbf{Ax} = \mathbf{b}$:
• ▪ Consistent if $\text{rank}(A) = \text{rank}([A|\mathbf{b}])$.
• ▪ Unique solution if $\text{rank}(A) = \text{rank}([A|\mathbf{b}]) = n$ (number of variables).
• ▪ Infinitely many solutions if $\text{rank}(A) = \text{rank}([A|\mathbf{b}]) < n$.
• ▪ Inconsistent if $\text{rank}(A) \neq \text{rank}([A|\mathbf{b}])$.

Common Pitfalls:

• Errors in Gaussian elimination leading to incorrect row echelon form.
• Misinterpreting the number of non-zero rows.
• Not considering the augmented matrix for system consistency.

Problem-Solving Techniques:

• The most reliable method is to reduce the matrix to row echelon form using Gaussian elimination and count the number of non-zero rows.
• For smaller matrices, checking determinants of submatrices can be faster.
• Use the Rank-Nullity Theorem to find nullity if rank is known, or vice versa.

Singular Value Decomposition (SVD)

Singular Value Decomposition is a powerful matrix factorization technique that decomposes any $m \times n$ matrix $A$ into three matrices: $U$, $\Sigma$, and $V^T$. It generalizes the concept of eigenvalues and eigenvectors to non-square matrices and has broad applications in data compression, noise reduction, and recommender systems.

• Definition: Any $m \times n$ matrix $A$ can be factored as $A = U\Sigma V^T$, where:

• $U$ is an $m \times m$ orthogonal matrix whose columns are the left singular vectors of $A$.

• $\Sigma$ is an $m \times n$ diagonal matrix with non-negative real numbers on the diagonal, called singular values ($\sigma_i$), arranged in decreasing order. The non-zero singular values are $\sigma_1 \geq \sigma_2 \geq \dots \geq \sigma_r > 0$, where $r = \text{rank}(A)$.

• $V$ is an $n \times n$ orthogonal matrix whose columns are the right singular vectors of $A$. $V^T$ is its transpose.

Relationship to Eigenvalues:

• The singular values $\sigma_i$ of $A$ are the square roots of the eigenvalues of $A^T A$ (or $AA^T$).
• The columns of $V$ are the eigenvectors of $A^T A$.
• The columns of $U$ are the eigenvectors of $AA^T$.

Properties/Applications:

• SVD exists for any matrix (square or rectangular).
• The number of non-zero singular values is equal to the rank of the matrix.
• Low-rank approximation: By keeping only the largest singular values and corresponding singular vectors, SVD can approximate a matrix with fewer components, useful for data compression.
• Pseudo-inverse: The SVD can be used to compute the Moore-Penrose pseudo-inverse of a matrix.
• Principal Component Analysis (PCA): SVD is closely related to PCA, where singular vectors correspond to principal components.

Common Pitfalls:

• Confusing singular values with eigenvalues.
• Incorrectly calculating eigenvectors for $A^T A$ or $AA^T$.
• Not arranging singular values in decreasing order.

Problem-Solving Techniques:

• Calculate $A^T A$ (or $AA^T$).
• Find the eigenvalues of $A^T A$. The square roots of these eigenvalues are the singular values $\sigma_i$.
• Find the eigenvectors of $A^T A$. These form the columns of $V$.
• Find the eigenvectors of $AA^T$. These form the columns of $U$.
• Alternatively, $U_i = \frac{1}{\sigma_i} A V_i$.

Statistics

While a broad field, within the context of linear algebra for GATE CS, statistics primarily involves concepts like mean, variance, covariance, and their matrix representations. These are crucial for understanding data analysis techniques like PCA, which heavily rely on linear algebra.

• Definition (Linear Algebra Context): Focuses on the mathematical tools (vectors, matrices) used to analyze and model data, particularly in multivariate statistics.

Key Concepts:

• 1. Mean: For a vector $\mathbf{x} = [x_1, \dots, x_n]^T$, the mean is $\bar{x} = \frac{1}{n} \sum_{i=1}^n x_i$.
• 2. Variance: A measure of how spread out the data is. For a vector $\mathbf{x}$, $\text{Var}(\mathbf{x}) = \frac{1}{n-1} \sum_{i=1}^n (x_i - \bar{x})^2$.
• 3. Covariance: A measure of how two variables change together. For two vectors $\mathbf{x}$ and $\\$mathbf{y}$,$\text{Cov}(\mathbf{x}, \mathbf{y}) = \frac{1}{n-1} \sum_{i=1}^n (x_i - \bar{x})(y_i - \bar{y})$.
• 4. Covariance Matrix: For a dataset with $p$ variables and $n$ observations, the covariance matrix $\Sigma$ is a $p \times p$ symmetric matrix where $\Sigma_{ij} = \text{Cov}(\mathbf{x}_i, \mathbf{x}_j)$ and $\\$Sigma_{ii} = \text{Var}(\mathbf{x}_i)$.

$\Sigma = \frac{1}{n - 1} X^T X$

where $X$ is the data matrix with columns centered (mean subtracted).

• 5. Principal Component Analysis (PCA): A dimensionality reduction technique that uses the eigenvectors of the covariance matrix (or SVD of the data matrix) to find orthogonal directions (principal components) of maximum variance in the data.

Properties:

• Covariance matrix is always symmetric and positive semi-definite.
• Eigenvalues of the covariance matrix represent the variance along the principal components.
• Eigenvectors of the covariance matrix are the principal components.

Common Pitfalls:

• Confusing variance with standard deviation.
• Incorrectly calculating covariance or covariance matrix.
• Not centering data before calculating covariance matrix for PCA.

Problem-Solving Techniques:

• Understand the definitions of mean, variance, and covariance.
• For PCA, compute the covariance matrix, then find its eigenvalues and eigenvectors.
• Relate SVD to PCA: SVD of the centered data matrix directly gives principal components and singular values related to variance.

Subspace

A subspace is a subset of a vector space that itself satisfies the properties of a vector space. It must contain the zero vector, be closed under vector addition, and closed under scalar multiplication. Subspaces are fundamental building

blocks for understanding the structure of vector spaces.

• Definition: A subset $W$ of a vector space $V$ is a subspace of $V$ if $W$ is itself a vector space under the operations defined on $V$.
• Conditions for a Subspace: A non-empty subset $W$ of a vector space $V$ is a subspace if and only if:
• 1. The zero vector of $V$ is in $W$ ($\mathbf{0} \in W$).
• 2. $W$ is closed under vector addition: If $\mathbf{u}, \mathbf{v} \in W$, then $\mathbf{u} + \mathbf{v} \in W$.
• 3. $W$ is closed under scalar multiplication: If $\mathbf{u} \in W$ and $c$ is any scalar, then $c\mathbf{u} \in W$.
• Important Subspaces Associated with a Matrix $A$:
• Column Space ($\text{Col}(A)$): The span of the column vectors of $A$. It is a subspace of $\mathbb{R}^m$ (if $A$ is $m \times n$). $\dim(\text{Col}(A)) = \text{rank}(A)$.
• Row Space ($\text{Row}(A)$): The span of the row vectors of $A$. It is a subspace of $\mathbb{R}^n$. $\dim(\text{Row}(A)) = \text{rank}(A)$.
• Null Space ($\text{Null}(A)$ or $\text{Ker}(A)$): The set of all vectors $\mathbf{x}$ such that $A\mathbf{x} = \mathbf{0}$. It is a subspace of $\mathbb{R}^n$. $\dim(\text{Null}(A)) = \text{nullity}(A)$.
• Left Null Space ($\text{Null}(A^T)$): The set of all vectors $\mathbf{y}$ such that $A^T\mathbf{y} = \mathbf{0}$. It is a subspace of $\mathbb{R}^m$.
• Properties:
• The intersection of two subspaces is always a subspace.
• The union of two subspaces is generally not a subspace.
• The sum of two subspaces $W_1 + W_2 = \{\mathbf{w}_1 + \mathbf{w}_2 \mid \mathbf{w}_1 \in W_1, \mathbf{w}_2 \in W_2\}$ is a subspace.
• Common Pitfalls:
• Forgetting to check all three conditions for a subspace (especially the zero vector).
• Confusing the column space with the null space.
• Assuming the union of subspaces is a subspace.
• Problem-Solving Techniques:
• To check if a set is a subspace, verify the three conditions.
• To find a basis for the column space, identify the pivot columns of the original matrix after reducing to REF.
• To find a basis for the null space, solve $A\mathbf{x} = \mathbf{0}$ and express the solution in terms of free variables.
• To find a basis for the row space, use the non-zero rows of the REF of the matrix.

System of Equations

A system of linear equations is a collection of one or more linear equations involving the same set of variables. Linear algebra provides powerful tools to determine the existence and nature of solutions (unique, infinite, or no solution) for such systems.

• Definition: A set of equations of the form $a_{11}x_1 + \dots + a_{1n}x_n = b_1, \dots, a_{m1}x_1 + \dots + a_{mn}x_n = b_m$. This can be written in matrix form as $A\mathbf{x} = \mathbf{b}$, where $A$ is the coefficient matrix, $\mathbf{x}$ is the vector of variables, and $\\$mathbf{b}$ is the constant vector.

• Types of Systems:

• Homogeneous System: $A\mathbf{x} = \mathbf{0}$. Always consistent (has at least the trivial solution $\mathbf{x} = \mathbf{0}$).

• Non-homogeneous System: $A\mathbf{x} = \mathbf{b}$ where $\mathbf{b} \neq \mathbf{0}$.

• Consistency and Number of Solutions (using Rank):

• 1. Consistent System: A system has at least one solution if $\text{rank}(A) = \text{rank}([A|\mathbf{b}])$.

• ▪ Unique Solution: If $\text{rank}(A) = \text{rank}([A|\mathbf{b}]) = n$ (number of variables).

• ▪ Infinitely Many Solutions: If $\text{rank}(A) = \text{rank}([A|\mathbf{b}]) < n$. The number of free variables is $n - \text{rank}(A)$.

• 2. Inconsistent System: A system has no solution if $\text{rank}(A) \neq \text{rank}([A|\mathbf{b}])$.

• Solution Methods:

• Gaussian Elimination/Row Reduction: Transform the augmented matrix $[A|\mathbf{b}]$ into row echelon form to solve by back-substitution.

• Matrix Inverse Method: If $A$ is square and invertible, $\mathbf{x} = A^{-1}\mathbf{b}$. (Only for unique solutions).

• Cramer's Rule: For a square system with a unique solution, $x_i = \frac{\det(A_i)}{\det(A)}$, where $A_i$ is the matrix formed by replacing the $i$-th column of $A$ with $\mathbf{b}$. (Computationally expensive for larger systems).

• Properties of Homogeneous Systems:

• Always has the trivial solution $\mathbf{x} = \mathbf{0}$.

• Has non-trivial solutions if and only if $\det(A) = 0$ (for square $A$) or $\text{rank}(A) < n$.

• The set of all solutions forms the null space of $A$.

• Common Pitfalls:

• Arithmetic errors during row operations.

• Incorrectly determining consistency or number of solutions.

• Applying Cramer's rule or inverse method when not applicable (e.g., non-square matrix, singular matrix).

Problem-Solving Techniques:

• Always form the augmented matrix $[A|\mathbf{b}]$.

• Use Gaussian elimination to reduce the augmented matrix to row echelon form.

• Analyze the rank of $A$ and $[A|\mathbf{b}]$ to determine consistency and number of solutions.

• For homogeneous systems, look for non-trivial solutions if $\det(A) = 0$ or $\text{rank}(A) < n$.

Vector Space

A vector space is a fundamental algebraic structure consisting of a set of vectors, along with two operations: vector addition and scalar multiplication, which satisfy a set of ten axioms. It provides a generalized framework for working with vectors beyond simple geometric arrows.

• Definition: A non-empty set $V$ of objects, called vectors, on which two operations are defined: vector addition (denoted by $+$) and scalar multiplication (denoted by juxtaposition), subject to ten axioms. The scalars are typically real numbers ($\mathbb{R}$) or complex numbers ($\mathbb{C}$).

• Axioms of a Vector Space: For all $\mathbf{u}, \mathbf{v}, \mathbf{w} \in V$ and all scalars $c, d$:

• 1. $\mathbf{u} + \mathbf{v} \in V$ (Closure under addition)
• 2. $\mathbf{u} + \mathbf{v} = \mathbf{v} + \mathbf{u}$ (Commutativity of addition)
• 3. $(\mathbf{u} + \mathbf{v}) + \mathbf{w} = \mathbf{u} + (\mathbf{v} + \mathbf{w})$ (Associativity of addition)
• 4. There exists a zero vector $\mathbf{0} \in V$ such that $\mathbf{u} + \mathbf{0} = \mathbf{u}$ (Additive identity)
• 5. For each $\mathbf{u} \in V$, there exists an additive inverse $-\mathbf{u} \in V$ such that $\mathbf{u} + (-\mathbf{u}) = \mathbf{0}$ (Additive inverse)
• 6. $c\mathbf{u} \in V$ (Closure under scalar multiplication)
• 7. $c(\mathbf{u} + \mathbf{v}) = c\mathbf{u} + c\mathbf{v}$ (Distributivity of scalar over vector addition)
• 8. $(c + d)\mathbf{u} = c\mathbf{u} + d\mathbf{u}$ (Distributivity of scalar over scalar addition)
• 9. $c(d\mathbf{u}) = (cd)\mathbf{u}$ (Associativity of scalar multiplication)
• 10. $1\mathbf{u} = \mathbf{u}$ (Multiplicative identity)

Key Concepts:

• Span: The set of all possible linear combinations of a set of vectors $\{\mathbf{v}_1, \dots, \mathbf{v}_k\}$. Denoted as $\text{span}\{\mathbf{v}_1, \dots, \mathbf{v}_k\}$. It is always a subspace.

• Linear Independence: A set of vectors $\{\mathbf{v}_1, \dots, \mathbf{v}_k\}$ is linearly independent if the only solution to $c_1\mathbf{v}_1 + \dots + c_k\mathbf{v}_k = \mathbf{0}$ is $c_1 = \dots = c_k = 0$.

• Basis: A set of vectors in a vector space $V$ that is linearly independent and spans $V$. The number of vectors in a basis is unique and is called the dimension of the vector space.

• Dimension: The number of vectors in any basis for a vector space $V$, denoted as $\dim(V)$.

Examples of Vector Spaces:

• $\mathbb{R}^n$ (n-dimensional real coordinate space)

• The set of all $m \times n$ matrices.

• The set of all polynomials of degree at most $n$.

• The set of all continuous functions on an interval.

Common Pitfalls:

• Forgetting to check all axioms when verifying if a set is a vector space.

• Confusing a vector space with a subspace.

• Incorrectly determining linear independence or a basis.

Problem-Solving Techniques:

• To check if a set is a vector space, verify all ten axioms.

• To check linear independence, set up the equation $c_1\mathbf{v}_1 + \dots + c_k\mathbf{v}_k = \mathbf{0}$ and solve the resulting system of linear equations.

• To find a basis, identify a linearly independent set that spans the space. For $\mathbb{R}^n$, this often involves finding pivot columns of a matrix formed by the vectors.

Quick Formula Reference

Determinant:

• $2 \times 2$: $|A| = ad - bc$ for $A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}$

• Properties: $|A^T| = |A|$, $|AB| = |A||B|$, $|kA| = k^n|A|$, $|A^{-1}| = 1/|A|$

• Invertible iff $|A| \neq 0$

Matrix Operations:

• Matrix Multiplication: $(AB)_{ij} = \sum_k A_{ik}B_{kj}$

• Inverse $2 \times 2$: $A^{-1} = \frac{1}{ad-bc} \begin{pmatrix} d & -b \\ -c & a \end{pmatrix}$

• General Inverse: $A^{-1} = \frac{1}{\det(A)} \operatorname{adj}(A)$

• Transpose Properties: $(A + B)^T = A^T + B^T$, $(AB)^T = B^T A^T$

• Inverse Properties: $(A^{-1})^{-1} = A$, $(AB)^{-1} = B^{-1} A^{-1}$

Eigenvalues & Eigenvectors:

• Characteristic Equation: $\det(A - \lambda I) = 0$

• Sum of Eigenvalues: $\sum \lambda_i = \operatorname{trace}(A)$

• Product of Eigenvalues: $\prod \lambda_i = \det(A)$

• Cayley-Hamilton Theorem: $P(A) = 0$ where $P(\lambda)$ is the characteristic polynomial.

• Algebraic Multiplicity (AM): Number of times $\lambda$ is a root.

• Geometric Multiplicity (GM): $\dim(\operatorname{Null}(A - \lambda I)) = n - \operatorname{rank}(A - \lambda I)$

• Diagonalizable if $\operatorname{AM}(\lambda) = \operatorname{GM}(\lambda)$ for all $\lambda$.

Rank of Matrix:

• Number of non-zero rows in REF.

• $\operatorname{rank}(A) \leq \min(m, n)$ for $m \times n$ matrix.

• Rank-Nullity Theorem: $\operatorname{rank}(A) + \operatorname{nullity}(A) = n$ (number of columns).

• System $A\mathbf{x} = \mathbf{b}$ consistent if $\operatorname{rank}(A) = \operatorname{rank}([A|\mathbf{b}])$.

• Unique solution if $\operatorname{rank}(A) = \operatorname{rank}([A|\mathbf{b}]) = n$.

• Infinite solutions if $\operatorname{rank}(A) = \operatorname{rank}([A|\mathbf{b}]) < n$.

• No solution if $\operatorname{rank}(A) \neq \operatorname{rank}([A|\mathbf{b}])$.

LU Decomposition:

• $A = LU$ (or $PA = LU$ with permutation matrix $P$)

• Solve $A\mathbf{x} = \mathbf{b}$ by $L\mathbf{y} = \mathbf{b}$ (forward substitution) then $U\mathbf{x} = \mathbf{y}$ (backward substitution).

Orthonormality:

• Orthogonal: $\mathbf{u} \cdot \mathbf{v} = 0$

• Normalized: $\|\mathbf{u}\| = 1$

• Orthonormal: $\mathbf{u}_i \cdot \mathbf{u}_j = \delta_{ij}$

• Orthogonal Matrix $Q$: $Q^T Q = I \implies Q^{-1} = Q^T$.

Singular Value Decomposition (SVD):

• $A = U\Sigma V^T$

• Singular values $\sigma_i$ are $\sqrt{\lambda_i(A^T A)}$.

• Columns of $V$ are eigenvectors of $A^T A$.

• Columns of $U$ are eigenvectors of $AA^T$.

Subspace Conditions:

• Contains zero vector.

• Closed under addition.

• Closed under scalar multiplication.

Important Tips for GATE

• Master the Basics: Ensure a strong understanding of fundamental definitions (e.g., matrix types, vector space axioms, linear independence). Many conceptual questions test these directly.

• Practice Gaussian Elimination: This is a core algorithm. Practice it diligently for solving systems, finding rank, and computing inverses. Accuracy and speed are crucial here.

• Understand Eigenvalue/Eigenvector Properties: Don't just memorize formulas. Understand why the sum of eigenvalues equals the trace and the product equals the determinant. These properties are often used as shortcuts or for verification.

• Pay Attention to Matrix Dimensions: Always check if matrix operations (addition, multiplication) are valid based on dimensions. This prevents common errors, especially in matrix multiplication.

• Rank-Nullity Theorem is Your Friend: This theorem is incredibly useful for quickly finding the nullity if the rank is known, or vice versa, and for analyzing the nature of solutions to linear systems.

• Beware of Calculation Errors: Linear algebra problems often involve extensive calculations. Use the virtual calculator carefully and double-check intermediate steps. Simple arithmetic mistakes are a common reason for losing marks.

• Distinguish Between Similar Concepts: Clearly differentiate between algebraic and geometric multiplicity, orthogonal and orthonormal vectors, and the various matrix subspaces (column space, null space, row space).

• Practice Previous Year Questions: Solve as many GATE previous year questions as possible. This will familiarize

you with the typical question patterns, difficulty levels, and time constraints. Focus on understanding the solution approach rather than just getting the answer.