Rank of a Matrix

The rank of a matrix is a single number that encapsulates much information about the relationships between a matrix's rows and columns and the dimensions of its fundamental subspaces. This concept can be thought of as a measure of the 'effective dimensions' or the amount of non-redundant information contained within a matrix.

Defining Matrix Rank

The rank of a matrix $A$, often denoted as $rank(A)$, can be defined in several equivalent ways, each offering a slightly different perspective:

1. Dimension of the Column Space: The rank is the dimension of the column space of $A$, denoted $dim(Col(A))$. This tells us the maximum number of linearly independent columns in $A$.
2. Dimension of the Row Space: The rank is also the dimension of the row space of $A$, denoted $dim(Row(A))$. This tells us the maximum number of linearly independent rows in $A$.

A fundamental result in linear algebra is that these two dimensions are always equal for any given matrix: $dim(Col(A)) = dim(Row(A)) = rank(A)$

So, the rank simultaneously tells you the number of linearly independent columns and the number of linearly independent rows.

Consider a dataset represented as a matrix $A$ where rows are samples and columns are features.

• $rank(A)$ tells you the number of linearly independent features. If the rank is less than the number of columns, some features can be expressed as linear combinations of others, indicating redundancy.
• $rank(A)$ also tells you the number of linearly independent samples (when viewed as row vectors).

Calculating the Rank

While rank is tied to the dimensions of the column and row spaces, calculating it directly from the definition by finding a basis can be tedious.

One way to think about rank calculation is through Gaussian elimination. When you reduce a matrix to its row echelon form, the number of non-zero rows (or equivalently, the number of pivots or leading 1s) is equal to the rank of the matrix. Each pivot corresponds to a linearly independent row (and column) in the context of the elimination process.

However, in practice, especially within a programming environment, we rely on numerical libraries to compute the rank reliably. Numerical methods, often based on techniques like Singular Value Decomposition (SVD, which we will cover in Chapter 6), are used because they are more stable in the presence of floating-point arithmetic.

In Python, NumPy's linear algebra module provides a straightforward function:

import numpy as np

# Example 1: Linearly independent columns/rows
A = np.array([[1, 0, 1],
              [0, 1, 1],
              [1, 1, 0]])
rank_A = np.linalg.matrix_rank(A)
# rank_A will be 3

# Example 2: Linearly dependent rows (row3 = row1 + row2)
B = np.array([[1, 2, 3],
              [4, 5, 6],
              [5, 7, 9]])
rank_B = np.linalg.matrix_rank(B)
# rank_B will be 2

# Example 3: Linearly dependent columns (col3 = col1 + col2)
C = np.array([[1, 4, 5],
              [2, 5, 7],
              [3, 6, 9]])
rank_C = np.linalg.matrix_rank(C)
# rank_C will be 2

print(f"Matrix A:\n{A}\nRank: {rank_A}\n")
print(f"Matrix B:\n{B}\nRank: {rank_B}\n")
print(f"Matrix C:\n{C}\nRank: {rank_C}")

Rank and Linear Independence

The connection between rank and linear independence is direct:

• For an $m \times n$ matrix $A$, if $rank(A) = n$, then the columns of $A$ are linearly independent.
• If $rank(A) < n$, the columns of $A$ are linearly dependent.
• Similarly, if $rank(A) = m$, the rows of $A$ are linearly independent.
• If $rank(A) < m$, the rows of $A$ are linearly dependent.

This is particularly relevant in machine learning when dealing with feature matrices. If the rank of your feature matrix is less than the number of features, it signals multicollinearity or redundant features. Some algorithms might struggle with rank-deficient matrices, and it often suggests that dimensionality reduction could be beneficial.

Full Rank and Rank Deficiency

A matrix $A$ with dimensions $m \times n$ is said to have full rank if its rank is the maximum possible value given its dimensions, i.e., $rank(A) = \min(m, n)$.

• Full Column Rank: If $rank(A) = n$ (requires $m \ge n$), the columns are linearly independent.
• Full Row Rank: If $rank(A) = m$ (requires $n \ge m$), the rows are linearly independent.

If $rank(A) < \min(m, n)$, the matrix is called rank deficient.

• A rank-deficient matrix implies linear dependencies among its columns and rows.
• For a square matrix ($n \times n$), being rank deficient ($rank(A) < n$) is equivalent to being non-invertible (or singular), meaning its determinant is zero (as discussed in Chapter 3). This also means the system $Ax=0$ has non-trivial solutions (related to the Null Space).

Rank in Machine Learning Applications

Understanding matrix rank helps interpret data structure and model properties:

• Feature Selection/Engineering: A rank-deficient feature matrix indicates that some features provide overlapping information. This might prompt feature removal or the use of dimensionality reduction techniques (like PCA, which relies on rank concepts via eigenvalues and SVD) to create a more compact, linearly independent set of features.
• Solvability of Systems: As seen in Chapter 3, the rank determines the nature of solutions to linear systems $Ax=b$. Comparing $rank(A)$ to $rank([A|b])$ (the augmented matrix) tells us if a system is consistent (has solutions). Comparing $rank(A)$ to the number of variables tells us if a consistent system has a unique solution or infinitely many. This is fundamental in solving for parameters in models like linear regression.
• Model Identifiability: In some statistical models, rank deficiency in design matrices can lead to non-identifiable parameters, meaning unique parameter estimates cannot be determined from the data alone.
• Matrix Factorization: Techniques like Non-negative Matrix Factorization (NMF) or methods used in recommender systems often assume or seek low-rank approximations of data matrices, explicitly using the concept of rank to capture the most significant underlying patterns.

In summary, the rank of a matrix is a simple number packing significant information. It quantifies the degree of linear independence within the rows and columns, determines the dimensions of the fundamental subspaces, and has direct implications for solving linear systems, understanding data redundancy, and evaluating the properties of machine learning models. As we move towards matrix decompositions like SVD, the concept of rank will reappear as a central theme.