Linear Algebra
Linear algebra is the mathematical discipline that deals with vectors, matrices, and the linear transformations between vector spaces. For GATE DA candidat...
Vectors, Matrices, and the Geometry of Data
Linear algebra is the mathematical discipline that deals with vectors, matrices, and the linear transformations between vector spaces. For GATE DA candidates, it is impossible to overstate its importance. Principal component analysis, linear regression, support vector machines, neural network weight updates, and graph algorithms all reduce to linear algebraic operations at their core.
A matrix A of size m x n represents a linear transformation from R^n to R^m. The action of the transformation on a vector x is the matrix-vector product Ax. Understanding this geometric interpretation is more powerful than memorizing rules. When A is a square matrix and Av = lambda * v for some non-zero vector v, v is called an eigenvector and lambda is the corresponding eigenvalue. Eigenvectors reveal the directions that the transformation stretches or compresses, and eigenvalues tell you by how much.
The rank of a matrix is the dimension of its column space, equivalently the number of linearly independent columns. Rank determines whether a system of equations has a unique solution, infinitely many solutions, or no solution. The rank-nullity theorem states that rank(A) + nullity(A) = n, where n is the number of columns. If A is m x n and rank(A) = n, the system Ax = b has a unique solution for any b in the column space.
Matrix decompositions are central to GATE DA. LU decomposition writes A = LU where L is lower triangular and U is upper triangular. Cholesky decomposition writes a positive definite matrix as A = LL^T. QR decomposition writes A = QR where Q is orthogonal and R is upper triangular. Singular value decomposition writes A = U Sigma V^T where U and V are orthogonal matrices and Sigma is diagonal with non-negative entries called singular values. SVD is used in PCA, latent semantic analysis, and recommender systems.
Practice tip: for any 2x2 or 3x3 matrix shown in an exam question, immediately check the trace and determinant. These two numbers constrain the eigenvalues and often allow you to answer questions about invertibility, positive definiteness, or rank without full computation.
Eigenvalues, Eigenvectors, and Matrix Decompositions for GATE
Computing eigenvalues requires solving the characteristic equation det(A - lambda I) = 0. For a 2x2 matrix with entries a, b, c, d, this gives the quadratic lambda^2 - (a+d)*lambda + (ad - bc) = 0. The two solutions are the eigenvalues. Once eigenvalues are known, eigenvectors are found by solving (A - lambda I)v = 0 for each lambda. GATE questions on eigenvalues often avoid full computation by exploiting properties: symmetric matrices always have real eigenvalues; the sum of eigenvalues equals the trace; the product of eigenvalues equals the determinant.
Diagonalization writes A = P D P^(-1) where D is a diagonal matrix of eigenvalues and P is a matrix whose columns are the corresponding eigenvectors. A matrix is diagonalizable if and only if it has n linearly independent eigenvectors. Symmetric matrices are always diagonalizable and their eigenvectors corresponding to distinct eigenvalues are orthogonal. This special case is called spectral decomposition: A = Q D Q^T where Q is orthogonal.
Singular value decomposition generalizes eigendecomposition to non-square matrices. Every matrix A of size m x n can be written as A = U Sigma V^T. The columns of U are the left singular vectors (eigenvectors of AA^T), the columns of V are the right singular vectors (eigenvectors of A^T A), and the diagonal entries of Sigma are the singular values, equal to the square roots of the eigenvalues of A^T A. The rank of A equals the number of non-zero singular values.
In PCA, you compute the covariance matrix C = (1/n) X^T X for a centered data matrix X. The eigenvectors of C are the principal components and the eigenvalues represent the variance explained by each component. Selecting the top k eigenvectors projects data onto a k-dimensional subspace that preserves maximum variance.
Worked example: if A has eigenvalues 4 and 1, then A^2 has eigenvalues 16 and 1, and A^(-1) has eigenvalues 1/4 and 1. This follows because if Av = lambda * v, then A^k v = lambda^k * v. GATE exploits this relationship in multiple question formats each year.
Systems of Linear Equations and Applications in Data Analysis
A system of linear equations Ax = b can be analyzed entirely through the lens of linear algebra. The system has a unique solution if A is square and invertible, equivalently if det(A) is non-zero. It has infinitely many solutions if b is in the column space of A but A is not invertible. It has no solution if b is outside the column space of A. This three-way classification is tested frequently in GATE DA.
Gaussian elimination is the standard algorithm for solving linear systems. It transforms A into row echelon form using elementary row operations. The number of non-zero rows in the echelon form equals the rank of A. The system is consistent if and only if rank(A) = rank([A|b]), where [A|b] is the augmented matrix. Cramer's rule gives an explicit formula for the solution using determinants, but it is computationally expensive and used mainly for 2x2 and 3x3 systems in exam settings.
Least squares solutions arise when Ax = b has no exact solution, a common situation in overdetermined systems where m > n. The normal equations A^T A x = A^T b give the vector x that minimizes the Euclidean distance ||Ax - b||^2. The solution is x = (A^T A)^(-1) A^T b when A has full column rank. The matrix (A^T A)^(-1) A^T is called the pseudoinverse of A, also written A^+.
Norms and inner products extend linear algebra to geometry. The inner product of vectors u and v is u^T v = sum of u_i v_i. Two vectors are orthogonal if their inner product is zero. The Gram-Schmidt process converts any linearly independent set of vectors into an orthonormal set while spanning the same subspace. Orthonormal bases simplify virtually every computation in linear algebra.
GATE DA question type: given that a 4x3 matrix A has rank 2, determine the nullity of A. By rank-nullity, nullity = 3 - 2 = 1. Then determine if Ax = 0 has a non-trivial solution. Since nullity is 1, yes it does. These two-step reasoning questions are common and rewarding once the fundamental theorem is internalized.