Matrices and Systems of Linear Equations

Overview

In this chapter, we shall explore the fundamental relationship between matrices and systems of linear equations. A system of linear equations, which may involve numerous variables, can be compactly and elegantly represented by a single matrix equation of the form $A\mathbf{x} = \mathbf{b}$. This representation is more than a mere notational convenience; it allows us to leverage the rich algebraic structure of matrices to systematically analyze and solve such systems. The properties of the coefficient matrix $A$ directly reveal profound insights into the nature of the solution set, determining whether a solution is unique, non-existent, or one of infinitely many.

A mastery of the concepts presented herein is indispensable for success in the GATE examination. The methods we will study form the algorithmic backbone for solving a significant portion of problems in linear algebra and its applications across various engineering disciplines. We will move beyond rote calculation to develop a conceptual understanding of how the structure of a matrix dictates the behavior of the system it represents. Our focus will be on the practical techniques and theoretical underpinnings required to solve problems with both accuracy and efficiency, a critical skill assessed in a competitive examination environment.

---

Chapter Contents

| # | Topic | What You'll Learn |
|---|-------|-------------------|
| 1 | Gaussian Elimination | Systematically solving linear systems via row operations. |
| 2 | Rank and Nullity | Analyzing the fundamental subspaces of a matrix. |
| 3 | Matrix Representation | Encoding linear transformations as structured arrays. |

---

Learning Objectives

---

We now turn our attention to Gaussian Elimination...

Part 1: Gaussian Elimination

Introduction

Gaussian elimination stands as a cornerstone algorithm in linear algebra, providing a systematic and computationally efficient method for solving systems of linear equations. Its fundamental purpose is to transform a given system, represented by an augmented matrix, into an equivalent, simpler system that can be solved with relative ease. This transformation is achieved by methodically applying a set of elementary row operations to reduce the matrix to what is known as row echelon form.

The procedure is not merely a tool for solving for unknown variables; its applications extend to other critical matrix computations relevant to the GATE examination, including the determination of a matrix's rank, the calculation of its determinant, and finding its inverse. A thorough understanding of this algorithm, including its operational steps and its computational complexity, is indispensable for tackling a wide range of problems in linear algebra and its applications in data science. We shall explore the mechanics of this method, analyze its efficiency, and discuss its implications for determining the nature of solutions to linear systems.

---

The Algorithm: Forward Elimination and Back Substitution

The process of Gaussian elimination is elegantly divided into two distinct phases. The first phase, Forward Elimination, aims to simplify the system by introducing zeros below the main diagonal of the coefficient matrix. The second phase, Back Substitution, involves solving the simplified upper triangular system for the unknown variables.

1. Phase I: Forward Elimination

The primary objective of forward elimination is to convert the augmented matrix $[A | \mathbf{b}]$ into an equivalent matrix $[U | \mathbf{c}]$ where $U$ is in row echelon form. This is accomplished using a sequence of elementary row operations.

The elementary row operations are:

Swapping: Interchanging two rows ($R_i \leftrightarrow R_j$).

Scaling: Multiplying a row by a non-zero scalar ($R_i \rightarrow kR_i$, where $k \neq 0$).

Replacement: Replacing one row with the sum of itself and a multiple of another row ($R_i \rightarrow R_i + kR_j$).

The algorithm proceeds by selecting a pivot element in the first column (typically $a_{11}$) and using the replacement operation to eliminate all entries below it. This process is then repeated for the submatrix formed by excluding the first row and first column, and so on, until the entire matrix is in row echelon form.

Original Matrix [A|b]
[
p
| *
[
x
| *
[
x
| *
→
R2 -> R2 - (x/p)R1
R3 -> R3 - (x/p)R1
After Step 1
[
p
| *
[
0
| *
[
0
| *
→
...
p
= Pivot Element
x
= Element to be eliminated

Worked Example (Forward Elimination):

Problem: Transform the following augmented matrix into row echelon form.

Solution:

Step 1: Use the pivot in the first row ($a_{11}=1$) to create zeros in the first column of rows 2 and 3. We perform the operations $R_2 \rightarrow R_2 - 2R_1$ and $R_3 \rightarrow R_3 - 3R_1$.

Step 2: Now, consider the submatrix. The next pivot is in the second row, second column ($a'_{22}=-2$). Use this pivot to create a zero below it. We perform the operation $R_3 \rightarrow R_3 - \frac{1}{2}R_2$.

Result: The matrix is now in row echelon form.

2. Phase II: Back Substitution

Once the augmented matrix is in row echelon form, $[U|\mathbf{c}]$, the system of equations is upper triangular and can be solved by starting from the last equation and substituting the results back into the equations above.

Worked Example (Back Substitution):

Problem: Solve the system represented by the row echelon form matrix obtained previously.

Solution:

The system of equations corresponding to this matrix is:

Step 1: Solve the last equation for $x_3$.

Step 2: Substitute the value of $x_3$ into the second-to-last equation and solve for $x_2$. (In this case, the second equation only depends on $x_2$).

Step 3: Substitute the values of $x_2$ and $x_3$ into the first equation and solve for $x_1$.

Result: The unique solution to the system is

---

---

Computational Complexity Analysis

For competitive examinations like GATE, understanding the computational cost of an algorithm is crucial. The complexity is typically measured by counting the number of floating-point arithmetic operations (multiplications, divisions, additions, and subtractions).

General Case: Dense $n \times n$ Matrix

Let us consider an $n \times n$ system. The forward elimination phase is the most computationally intensive part. To eliminate the entries below the pivot in the first column, we perform $(n-1)$ row operations. Each row operation involves one division (to find the multiplier) and $n$ multiplications and $n$ additions across the row. This is repeated for each of the $n-1$ pivots.

The number of operations can be approximated by the sums:

• Multiplications/Divisions: $\sum_{k=1}^{n-1} (n-k)(n-k+1) \approx \frac{n^3}{3}$


• Additions/Subtractions: $\sum_{k=1}^{n-1} (n-k)(n-k) \approx \frac{n^3}{3}$

The total number of operations for forward elimination is therefore proportional to $n^3$, which we denote as $O(n^3)$.

For back substitution, we solve for $x_n$, then $x_{n-1}$, and so on. To solve for $x_i$, it requires $(n-i)$ multiplications, $(n-i)$ subtractions, and one division.

• Total operations: $\sum_{i=1}^{n} (2(n-i)+1) \approx n^2$.

The complexity of back substitution is thus $O(n^2)$.

Since the forward elimination phase dominates, the overall complexity of Gaussian elimination for a general $n \times n$ matrix is $O(n^3)$.

Special Case: Upper Triangular Matrix

A critical observation, often tested in GATE, concerns the complexity for special matrix structures. Consider an $n \times n$ matrix that is already in upper triangular form.

In this scenario, the matrix is already in a state where no elements exist below the main diagonal. Consequently, the entire forward elimination phase is redundant and can be skipped. The algorithm proceeds directly to the back substitution phase.

As we established, the complexity of back substitution is $O(n^2)$. Therefore, performing "Gaussian elimination" on an already upper triangular matrix to solve a system $A\mathbf{x} = \mathbf{b}$ involves only back substitution, and its complexity is $O(n^2)$.

---

Problem-Solving Strategies

---

Common Mistakes

---

Practice Questions

:::question type="MCQ" question="Consider the augmented matrix for a system of linear equations:

. After performing the first step of forward elimination to create zeros below the first pivot, what is the entry in the second row, third column?" options=["2","3","-2","8"] answer="2" hint="The first pivot is 2. Perform the operation $R_2 \rightarrow R_2 - (1/2)R_1$. Calculate the new value for the element at position (2,3)." solution="
Step 1: Identify the pivot and the target row. The pivot is $a_{11} = 2$. We want to modify Row 2.

Step 2: Determine the row operation. The operation is $R_2 \rightarrow R_2 - \frac{a_{21}}{a_{11}}R_1$.

Step 3: Apply this operation to the third element of Row 2. The original element is $a_{23} = 5$. The corresponding element in Row 1 is $a_{13} = 6$.

Result: The new entry in the second row, third column is 2.
Answer: \boxed{2}
"
:::

:::question type="NAT" question="A system of equations is reduced to the following row echelon form:

. What is the value of the variable $x_2$?" answer="-1" hint="This requires back substitution. First, solve for $x_3$ from the last row. Then, substitute this value into the equation from the second row to find $x_2$." solution="
Step 1: Write down the equations from the row echelon form.

Step 2: Solve for $x_3$ using the third equation.

Step 3: Substitute the value of $x_3$ into the second equation to solve for $x_2$.

Result: The value of $x_2$ is -1.
Answer: \boxed{-1}
"
:::

:::question type="MSQ" question="The augmented matrix of a system of linear equations is reduced to the form

. Which of the following statements is/are correct?" options=["The system is inconsistent.","The system has infinitely many solutions.","The system has 2 free variables.","The rank of the coefficient matrix is 3."] answer="The system has infinitely many solutions.,The system has 2 free variables." hint="Analyze the $\operatorname{rank}$ of the coefficient matrix and the augmented matrix. The number of free variables is the total number of variables minus the $\operatorname{rank}$." solution="
Analysis:

The coefficient matrix has 2 non-zero rows, so its $\operatorname{rank}$ is $r=2$.

The augmented matrix also has 2 non-zero rows, so its $\operatorname{rank}$ is also 2. Since $\operatorname{rank}(A) = \operatorname{rank}(\left[A|\mathbf{b}\right])$, the system is consistent. This eliminates the 'inconsistent' option.

The number of variables is $n=4$ (corresponding to the four columns in A).

Since $r < n$ ($2 < 4$), the system has infinitely many solutions.

The number of free variables is $n - r = 4 - 2 = 2$. The pivot columns are column 1 and column 3. The non-pivot columns, column 2 ($x_2$) and column 4 ($x_4$), correspond to the free variables.

The $\operatorname{rank}$ of the coefficient matrix is 2, not 3.

Therefore, the correct statements are that the system has infinitely many solutions and has 2 free variables.
Answer: \boxed{\text{The system has infinitely many solutions.,The system has 2 free variables.}}
"
:::

:::question type="MCQ" question="What is the order of computational complexity for solving a system of linear equations $A\mathbf{x}=\mathbf{b}$ where $A$ is an $n \times n$ lower triangular matrix?" options=["$O(n)$","$O(n^2)$","$O(n^3)$","$O(\log n)$"] answer="$O(n^2)$" hint="A lower triangular system is similar to an upper triangular one, but the solving process is reversed. Analyze the complexity of this 'forward substitution' process." solution="
Step 1: A system with a lower triangular matrix $L$ has the form:

Step 2: This system can be solved directly without an elimination phase. The process is called forward substitution. We first solve for $x_1$, then substitute its value into the second equation to solve for $x_2$, and so on.

Step 3: Let's analyze the complexity of this process.

• To find $x_1$: 1 division.


• To find $x_2$: 1 multiplication, 1 subtraction, 1 division.


• To find $x_k$: $(k-1)$ multiplications, $(k-1)$ subtractions, 1 division.

Step 4: The total number of operations is approximately $\sum_{k=1}^{n} 2(k-1)$, which is proportional to $n^2$.

Result: The complexity is $O(n^2)$, analogous to the back substitution process for upper triangular matrices.
Answer: \boxed{O(n^2)}
"
:::

---

Summary

---

What's Next?

---

---

Part 2: Rank and Nullity

Introduction

In the study of linear algebra, the concepts of rank and nullity are of central importance. They provide a quantitative measure of the fundamental properties of a matrix and the linear transformation it represents. The rank of a matrix can be understood as a measure of its "non-degeneracy," quantifying the dimension of the output space of the transformation. Conversely, the nullity measures the dimension of the input space that is mapped to the zero vector, representing the "degeneracy" of the transformation.

Together, these concepts are encapsulated in the Rank-Nullity Theorem, a cornerstone result that establishes a profound relationship between the dimensions of the domain, the image (column space), and the kernel (null space) of a linear map. For the GATE examination, a firm grasp of rank and nullity is indispensable for analyzing systems of linear equations, determining matrix invertibility, and understanding the structure of vector spaces associated with matrices. We shall explore these concepts, their properties, and their direct applications to problem-solving.

---

---

Key Concepts

1. The Rank-Nullity Theorem

The Rank-Nullity Theorem provides a fundamental relationship between the rank and nullity of a matrix. It connects the dimensions of the two primary subspaces associated with any matrix: the column space and the null space.

Domain $\mathbb{R}^n$

Codomain $\mathbb{R}^m$

Null Space
(Kernel)
dim = nullity(A)

Column Space
(Image)
dim = rank(A)

Matrix A







0

Worked Example:

Problem: Find the rank and nullity of the matrix $A = \begin{pmatrix} 1 & 2 & 1 & 3 \\ 1 & 3 & 2 & 4 \\ 2 & 5 & 3 & 7 \end{pmatrix}$.

Solution:

We will use Gaussian elimination to find the row echelon form of the matrix. The number of non-zero rows will be the rank.

Step 1: Start with the given matrix.

Step 2: Apply row operations to create zeros below the first pivot.
Apply $R_2 \rightarrow R_2 - R_1$ and $R_3 \rightarrow R_3 - 2R_1$.

Step 3: Apply a row operation to create a zero below the second pivot.
Apply $R_3 \rightarrow R_3 - R_2$.

Step 4: Identify the rank.
The matrix is now in row echelon form. We count the number of non-zero rows. There are two non-zero rows.

Step 5: Apply the Rank-Nullity Theorem.
The matrix $A$ is of size $3 \times 4$. Thus, $m=3$ and $n=4$.

Answer: The rank of the matrix is 2, and the nullity is 2.

---

2. Rank and Systems of Linear Equations

The concept of rank is fundamental to determining the nature of solutions for a system of linear equations, $A\mathbf{x} = \mathbf{b}$.

Let us consider a consistent system where $\operatorname{rank}(A) = \operatorname{rank}\left[A \middle| \mathbf{b}\right] = r$. Let $n$ be the number of variables (columns of $A$).

Unique Solution: The system has a unique solution if and only if $r = n$. In this case, there are no free variables. For a square matrix ($m=n$), this occurs when $A$ is invertible (full rank).

Infinite Solutions: The system has infinitely many solutions if and only if $r < n$. The number of free variables, which determines the dimensionality of the solution set, is given by $n-r$. This quantity is precisely the nullity of $A$.

This analysis is critical for understanding questions that probe the existence and uniqueness of solutions for different matrices and vectors, as seen in GATE.

| Case | Matrix `$A$` | `$\operatorname{rank}(A) = r$` | Condition | Nature of Solutions for `$A\mathbf{x} = \mathbf{b}$` |
| :--- | :--- | :--- | :--- | :--- |
| 1 | Square (`$n \times n$`) | `$r=n$` | Invertible | Unique solution for every `$\mathbf{b}$`. |
| 2 | Square (`$n \times n$`) | `$r<n$` | Singular | No solution for some `$\mathbf{b}$`, infinite solutions for other `$\mathbf{b}$`. |
| 3 | Wide (`$m \times n, m<n$`) | `$r \le m < n$` | - | No solution or infinite solutions. Never a unique solution. |
| 4 | Tall (`$m \times n, m>n$`) | `$r=n$` | Full column rank | Unique solution or no solution. |
| 5 | Tall (`$m \times n, m>n$`) | `$r<n$` | Rank deficient | Infinite solutions or no solution. |

---

3. Properties of Rank and Nullity

Understanding the properties of rank is essential for solving more abstract problems.

Let $A$ be an $m \times n$ matrix and $B$ be an $n \times p$ matrix.

• Bounds: $0 \le \operatorname{rank}(A) \le \min(m, n)$.
• Transpose: $\operatorname{rank}(A) = \operatorname{rank}(A^T)$.
• Matrix Product (Sylvester's Inequality): $\operatorname{rank}(A) + \operatorname{rank}(B) - n \le \operatorname{rank}(AB) \le \min(\operatorname{rank}(A), \operatorname{rank}(B))$. The second inequality is most frequently used.
• Invertibility: An $n \times n$ matrix $A$ is invertible if and only if $\operatorname{rank}(A) = n$. This is equivalent to $\operatorname{nullity}(A) = 0$ or $\det(A) \ne 0$.
• Matrix Powers: For a square matrix $A$, we have $\operatorname{rank}(A) \ge \operatorname{rank}(A^2) \ge \operatorname{rank}(A^3) \ge \dots$. The ranks are non-increasing. A particularly important result, relevant to GATE questions, is that if for some $k \ge 1$, $\operatorname{rank}(A^k) = \operatorname{rank}(A^{k+1})$, then $\operatorname{rank}(A^k) = \operatorname{rank}(A^j)$ for all $j > k$.
• Relation between Column Spaces: The column space of $AB$, $C(AB)$, is a subspace of the column space of $A$, $C(A)$. Similarly, the null space of $B$, $N(B)$, is a subspace of the null space of $AB$, $N(AB)$.
• A Special Condition: A condition like $A^3=A$ implies a stable structure for the column space. If $\mathbf{y} \in C(A)$, then $\mathbf{y} = A\mathbf{x}$ for some $\mathbf{x}$. The condition $A^3=A$ gives $\mathbf{y} = A\mathbf{x} = A^3\mathbf{x} = A^2(A\mathbf{x}) = A^2\mathbf{y}$. This means every vector in the column space of $A$ is also in the column space of $A^2$. Since we always have $C(A^2) \subseteq C(A)$, this forces the equality $C(A^2) = C(A)$, which in turn implies $\operatorname{rank}(A^2) = \operatorname{rank}(A)$.

---

4. Rank, Nullity, and Eigenvalues

The nullity of a matrix is directly connected to its eigenvalues.

This connection is frequently tested. For instance, if a problem provides information that implies a matrix must have an eigenvalue of 0, we can immediately conclude that its nullity is at least 1, its rank is less than $n$, and the homogeneous system $A\mathbf{x}=\mathbf{0}$ has infinitely many solutions.

Eigenvalues of Polynomials of Matrices:
If $A$ has an eigenvalue $\lambda$ with corresponding eigenvector $\mathbf{v}$, and $P(t)$ is a polynomial, then $P(A)$ has an eigenvalue $P(\lambda)$ with the same eigenvector $\mathbf{v}$.
For example, if $B = A^3 - 2A^2 + A$, and $\lambda$ is an eigenvalue of $A$, then $\mu = \lambda^3 - 2\lambda^2 + \lambda$ is an eigenvalue of $B$.

A Common GATE Scenario:
If the sum of elements in each row of a matrix $A$ is a constant $k$, then $k$ is an eigenvalue of $A$, and the vector $\mathbf{v} = [1, 1, \dots, 1]^T$ is the corresponding eigenvector.
To see this, consider the product $A\mathbf{v}$. The $i$-th entry of the resulting vector is $\sum_{j=1}^{n} A_{ij}v_j = \sum_{j=1}^{n} A_{ij}(1)$, which is the sum of the elements in the $i$-th row of $A$. If this sum is $k$ for all rows, then $A\mathbf{v} = k\mathbf{v}$.

---

---

Problem-Solving Strategies

---

Common Mistakes

---

Practice Questions

:::question type="MCQ" question="Let $A$ be a $5 \times 5$ real matrix such that $A^2 = A$ (an idempotent matrix). Which of the following statements is NOT always true?" options=["$\operatorname{rank}(A) + \operatorname{rank}(I-A) = 5$", "The null space of $A$ is a subset of the column space of $(I-A)$", "$A$ is invertible", "The only possible eigenvalues of $A$ are $0$ and $1$"] answer="$A$ is invertible" hint="Consider the properties of idempotent matrices. What happens if you choose $A$ to be the zero matrix? Also, analyze the equation $A\mathbf{x}=\lambda\mathbf{x}$ by multiplying by $A$ again." solution="
Step 1: Analyze the condition $A^2 = A$. This can be rewritten as $A(A-I) = 0$.

Step 2: Analyze the eigenvalues. Let $\lambda$ be an eigenvalue of $A$ with eigenvector $\mathbf{x}$.

Multiplying by $A$, we get

Since $A^2 = A$, we have

Therefore,

which implies

Since $\mathbf{x}$ is an eigenvector, it is non-zero, so we must have

or

The only possible eigenvalues are $\lambda=0$ and $\lambda=1$. So, option D is always true.

Step 3: Analyze invertibility. If $A$ is the zero matrix, $A^2 = 0 = A$, so the condition is satisfied. The zero matrix is not invertible. If $A$ is the identity matrix $I$, then $I^2 = I$, and $I$ is invertible. Since $A$ can be singular, the statement '$A$ is invertible' is not always true. This makes C the likely answer.

Step 4: Analyze the other options for completeness.
For an idempotent matrix, it is a standard result that $\mathbb{R}^n = C(A) \oplus N(A)$, where $C(A)$ is the column space and $N(A)$ is the null space.
Also, it can be shown that $N(A) = C(I-A)$ and $N(I-A) = C(A)$.
The rank is the dimension of the column space. So, $\operatorname{rank}(A) = \dim(C(A))$ and $\operatorname{rank}(I-A) = \dim(C(I-A)) = \dim(N(A)) = \operatorname{nullity}(A)$.
By the Rank-Nullity theorem, $\operatorname{rank}(A) + \operatorname{nullity}(A) = 5$.
Substituting, we get $\operatorname{rank}(A) + \operatorname{rank}(I-A) = 5$. So, option A is always true.
From $N(A) = C(I-A)$, it is clear that the null space of $A$ is not just a subset but is equal to the column space of $(I-A)$. So, option B is always true.

Result: The statement that is not always true is that $A$ is invertible.
Answer: \boxed{A \text{ is invertible}}
"
:::

:::question type="NAT" question="Let $A$ be a $4 \times 5$ matrix with $\operatorname{rank}(A) = 3$. If the system $A\mathbf{x}=\mathbf{b}$ is consistent, what is the dimension of the solution space for the corresponding homogeneous system $A\mathbf{x}=\mathbf{0}$?" answer="2" hint="The dimension of the solution space of a homogeneous system is its nullity. Use the Rank-Nullity theorem." solution="
Step 1: Identify the given parameters.
The matrix $A$ has dimensions $m \times n$, where $m=4$ and $n=5$.
The rank of the matrix is given: $\operatorname{rank}(A) = 3$.

Step 2: Understand the question.
The 'dimension of the solution space for the homogeneous system $A\mathbf{x}=\mathbf{0}$' is the definition of the nullity of matrix $A$.

Step 3: Apply the Rank-Nullity Theorem.
The theorem states: $\operatorname{rank}(A) + \operatorname{nullity}(A) = n$ (number of columns).

Step 4: Substitute the values and solve for nullity.

Result: The dimension of the solution space is 2.
Answer: \boxed{2}
"
:::

:::question type="MSQ" question="Let $A \in \mathbb{R}^{3 \times 4}$, $B \in \mathbb{R}^{4 \times 3}$, and $C \in \mathbb{R}^{3 \times 3}$. Let $\operatorname{rank}(A)=3$ and $\operatorname{rank}(B)=2$. Which of the following statements is/are necessarily TRUE?" options=["The system $A\mathbf{x}=\mathbf{b}$ has infinite solutions for every $\mathbf{b} \in \mathbb{R}^3$.","The system $B\mathbf{y}=\mathbf{d}$ can have a unique solution for some $\mathbf{d} \in \mathbb{R}^4$.","$\operatorname{rank}(AC)$ can be 3.","$\operatorname{rank}(AB)$ is at most 2."] answer="A,D" hint="For A, consider the dimensions and rank of A. For B, consider the dimensions of B. For C and D, use the property $\operatorname{rank}(XY) \le \min(\operatorname{rank}(X), \operatorname{rank}(Y))$." solution="
Analysis of Option A:
$A$ is a $3 \times 4$ matrix with $\operatorname{rank}(A)=3$. The number of rows is $m=3$. Since $\operatorname{rank}(A)=m$, the columns of $A$ span the entire codomain $\mathbb{R}^3$. This means that for any vector $\mathbf{b} \in \mathbb{R}^3$, the system $A\mathbf{x}=\mathbf{b}$ is consistent. The number of variables is $n=4$. Since $\operatorname{rank}(A) = 3 < n=4$, there must be $n - \operatorname{rank}(A) = 4-3=1$ free variable. Therefore, the system has infinite solutions for every $\mathbf{b}$. Statement A is TRUE.

Analysis of Option B:
$B$ is a $4 \times 3$ matrix. The system is $B\mathbf{y}=\mathbf{d}$, where $\mathbf{y} \in \mathbb{R}^3$. The number of variables is $n=3$. For a unique solution, we need $\operatorname{rank}(B) = n = 3$. However, it is given that $\operatorname{rank}(B)=2$. Since $\operatorname{rank}(B) < n$, the system, if consistent, must have infinite solutions. It can never have a unique solution. Statement B is FALSE.

Analysis of Option C:
$C$ is a $3 \times 3$ matrix. We consider the product $AC$. The size of $AC$ is $(3 \times 4) \times (3 \times 3)$, which is not a valid matrix multiplication. Let's assume the question meant $CA$, where $C$ is $4 \times 3$. Or perhaps $C$ is $4 \times 4$. Assuming the question intended $A \in \mathbb{R}^{3 \times 3}, B \in \mathbb{R}^{3 \times 4}, C \in \mathbb{R}^{4 \times 3}$ and $\operatorname{rank}(A)=3, \operatorname{rank}(C)=2$. Then $\operatorname{rank}(AC) \le \min(\operatorname{rank}(A), \operatorname{rank}(C)) = \min(3,2)=2$. Let's stick to the original dimensions. The product $AC$ is not defined. If the question intended a product like $C'A$ with $C' \in \mathbb{R}^{k \times 3}$, then $\operatorname{rank}(C'A) \le \min(\operatorname{rank}(C'), \operatorname{rank}(A)) \le \operatorname{rank}(A)=3$. But we cannot be certain. Let's re-read the question carefully. $A \in \mathbb{R}^{3 \times 4}, C \in \mathbb{R}^{3 \times 3}$. The product $AC$ is not defined. Let's assume it was a typo for $CA$ where $C \in \mathbb{R}^{4 \times 3}$. Then $\operatorname{rank}(CA) \le \min(\operatorname{rank}(C), \operatorname{rank}(A))$. Or maybe the typo was $A \in \mathbb{R}^{3 \times 3}$. Let's assume the question is flawed as written and move on. Let's assume it was $C \in \mathbb{R}^{4 \times k}$ and the product was $AC$. Then $\operatorname{rank}(AC) \le \min(\operatorname{rank}(A), \operatorname{rank}(C)) \le \operatorname{rank}(A)=3$. It is possible for the rank to be 3 if $C$ is, for example, a $4 \times 4$ identity matrix. But the question gives $C \in \mathbb{R}^{3 \times 3}$. Given the ambiguity, let's assume the intended product was valid, such as $C_{3 \times 3} A_{3 \times 4}$. Then $\operatorname{rank}(CA) \le \min(\operatorname{rank}(C), \operatorname{rank}(A)) = \min(\operatorname{rank}(C), 3)$. If $C$ is invertible, $\operatorname{rank}(C)=3$, and $\operatorname{rank}(CA)=\operatorname{rank}(A)=3$. So it is possible. But is it necessarily true? No. If $C$ is the zero matrix, the rank is 0. Let's re-evaluate option D.

Analysis of Option D:
We are considering the product $AB$. $A$ is $3 \times 4$ and $B$ is $4 \times 3$. The product $AB$ is a $3 \times 3$ matrix.
Using the rank property:

This means the rank of $AB$ is at most 2. Statement D is TRUE.

Conclusion: Statements A and D are necessarily true.
Answer: \boxed{A,D}
"
:::

---

Summary

---

---

What's Next?

---

---

Part 3: Matrix Representation

Introduction

In the study of linear algebra, linear transformations are fundamental objects that describe structure-preserving maps between vector spaces. While these transformations can be defined abstractly, their true computational power is unlocked when we can represent them in a concrete, numerical form. The matrix representation of a linear transformation provides this bridge from the abstract to the concrete.

By choosing an ordered basis for both the domain and codomain vector spaces, we can associate a unique matrix with any given linear transformation. This matrix encapsulates all the information about the transformation. Consequently, the abstract operation of applying a transformation to a vector becomes the familiar and straightforward process of matrix-vector multiplication. This concept is not merely a notational convenience; it is a cornerstone of computational linear algebra, enabling us to analyze and solve complex problems involving linear systems, differential equations, and data analysis.

---

Key Concepts

1. Constructing the Matrix Representation

The definition itself provides a direct procedure for constructing the matrix. The core task is to determine how the transformation $T$ acts on each basis vector of the domain $V$. The resulting vectors, which lie in the codomain $W$, are then expressed in terms of the basis vectors of $W$. The coefficients of these linear combinations form the columns of the matrix representation.

This construction establishes a fundamental relationship: for any vector $v \in V$, the coordinate vector of its image $T(v)$ can be found by multiplying the matrix representation of $T$ by the coordinate vector of $v$.

The following diagram illustrates this commutative relationship. Moving from $v$ to $T(v)$ in the abstract vector space (top path) is equivalent to moving from $[v]_{\mathcal{B}}$ to $[T(v)]_{\mathcal{C}}$ via matrix multiplication in the coordinate space (bottom path).

V
W


$\mathbb{R}^n$
$\mathbb{R}^m$




T (Transformation)



Multiplication by $[T]_{\mathcal{B}}^{\mathcal{C}}$



Coord$_{B}$



Coord$_{C}$

Worked Example:

Problem: Let $T: \mathbb{R}^2 \to \mathbb{R}^3$ be a linear transformation defined by $T(x, y) = (x+2y, 3x-y, y)$. Find the matrix representation of $T$ with respect to the standard basis $\mathcal{B} = \{e_1, e_2\}$ for $\mathbb{R}^2$ and the standard basis $\mathcal{C} = \{f_1, f_2, f_3\}$ for $\mathbb{R}^3$.

Here, $e_1 = (1, 0)$, $e_2 = (0, 1)$, and $f_1 = (1, 0, 0)$, $f_2 = (0, 1, 0)$, $f_3 = (0, 0, 1)$.

Solution:

Step 1: Apply the transformation $T$ to the first basis vector of the domain, $e_1$.

Step 2: Express the result $T(e_1)$ as a linear combination of the basis vectors of the codomain, $\mathcal{C}$. The coordinate vector $[T(e_1)]_{\mathcal{C}}$ will form the first column of our matrix.

Step 3: Apply the transformation $T$ to the second basis vector of the domain, $e_2$.

Step 4: Express the result $T(e_2)$ as a linear combination of the basis vectors of the codomain, $\mathcal{C}$. The coordinate vector $[T(e_2)]_{\mathcal{C}}$ will form the second column of our matrix.

Step 5: Assemble the matrix $[T]_{\mathcal{B}}^{\mathcal{C}}$ using the coordinate vectors from Step 2 and Step 4 as its columns.

Answer:

---

---

Problem-Solving Strategies

---

Common Mistakes

---

Practice Questions

:::question type="MCQ" question="Let $T: \mathbb{P}_2 \to \mathbb{R}^2$ be a linear transformation defined by $T(p(x)) = (p(0), p'(1))$, where $\mathbb{P}_2$ is the space of polynomials of degree at most 2. Let $\mathcal{B} = \{1, x, x^2\}$ be the standard basis for $\mathbb{P}_2$ and $\mathcal{C} = \{(1,0), (0,1)\}$ be the standard basis for $\mathbb{R}^2$. What is the entry in the second row and third column of the matrix $[T]_{\mathcal{B}}^{\mathcal{C}}$?" options=["0", "1", "2", "-1"] answer="2" hint="The third column is determined by the image of the third basis vector of the domain, $x^2$. Find $T(x^2)$ and then its coordinates with respect to the standard basis of $\mathbb{R}^2$." solution="
Step 1: Identify the third basis vector of the domain $\mathbb{P}_2$.
The basis is $\mathcal{B} = \{1, x, x^2\}$, so the third basis vector is $v_3 = p(x) = x^2$.

Step 2: Apply the transformation $T$ to this basis vector.
For $p(x) = x^2$, we have $p(0) = 0^2 = 0$. The derivative is $p'(x) = 2x$, so $p'(1) = 2(1) = 2$.
Therefore, $T(x^2) = (p(0), p'(1)) = (0, 2)$.

Step 3: Find the coordinate vector of $T(x^2)$ with respect to the codomain basis $\mathcal{C} = \{(1,0), (0,1)\}$.

The coordinate vector is

Step 4: This coordinate vector forms the third column of the matrix $[T]_{\mathcal{B}}^{\mathcal{C}}$.
The matrix has the form

Result: The entry in the second row and third column is 2.
Answer: \boxed{2}
"
:::

:::question type="NAT" question="Consider the linear transformation $T: \mathbb{R}^2 \to \mathbb{R}^2$ that reflects vectors across the line $y=x$. Let $\mathcal{B} = \{(1, 2), (0, 1)\}$ be a basis for the domain and $\mathcal{C} = \{(1, 0), (0, 1)\}$ (the standard basis) be the basis for the codomain. Calculate the value of the entry in the first row, first column of the matrix $[T]_{\mathcal{B}}^{\mathcal{C}}$." answer="2" hint="The transformation that reflects $(a,b)$ across $y=x$ is $T(a,b)=(b,a)$. Apply this to the first basis vector of $\mathcal{B}$ and find its coordinates with respect to $\mathcal{C}$." solution="
Step 1: Define the action of the transformation $T$.
A reflection across the line $y=x$ maps a point $(a,b)$ to $(b,a)$. So, $T(a,b) = (b,a)$.

Step 2: Identify the first basis vector of the domain, $v_1$.
From $\mathcal{B} = \{(1, 2), (0, 1)\}$, we have $v_1 = (1, 2)$.

Step 3: Apply the transformation $T$ to $v_1$.

Step 4: Find the coordinate vector of $T(v_1)$ with respect to the codomain basis $\mathcal{C} = \{(1,0), (0,1)\}$.
Since $\mathcal{C}$ is the standard basis, the coordinates are simply the components of the vector.

So,

Step 5: This vector is the first column of the matrix $[T]_{\mathcal{B}}^{\mathcal{C}}$.
The entry in the first row, first column is the first component of this vector.

Result: The value is 2.
Answer: \boxed{2}
"
:::

---

Summary

---

---

What's Next?

---

Chapter Summary

---

Chapter Review Questions

:::question type="MCQ" question="Consider the system of linear equations:

For which of the following values of $\lambda$ and $\mu$ does the system have infinitely many solutions?" options=["$\lambda = 3, \mu = 10$","$\lambda = 3, \mu \neq 10$","$\lambda \neq 3, \mu = 10$","$\lambda \neq 3, \mu \neq 10$"] answer="A" hint="For infinitely many solutions, the system must be consistent, and the rank of the coefficient matrix must be less than the number of variables. Use Gaussian elimination on the augmented matrix." solution="
We begin by writing the augmented matrix $[A|\mathbf{b}]$ for the given system:

Now, we apply Gaussian elimination to reduce the matrix to its row echelon form.
Perform the row operations $R_2 \leftarrow R_2 - R_1$ and $R_3 \leftarrow R_3 - R_1$:

Next, perform the operation $R_3 \leftarrow R_3 - R_2$:

For the system to have infinitely many solutions, it must be consistent and the rank of the coefficient matrix $A$ must be less than the number of variables ($n=3$).
From the echelon form, we see that $\operatorname{rank}(A)$ will be less than 3 if and only if the last row of the coefficient part is all zeros. This requires:

When $\lambda=3$, the rank of $A$ is 2.
For the system to be consistent, we must have $\operatorname{rank}(A) = \operatorname{rank}([A|\mathbf{b}])$. This means the last entry in the augmented part must also be zero.

Thus, for infinitely many solutions, we need $\lambda = 3$ and $\mu = 10$. In this case, $\operatorname{rank}(A) = \operatorname{rank}([A|\mathbf{b}]) = 2 < 3$.
"
:::

:::question type="NAT" question="Let $A$ be a $4 \times 5$ real matrix. The set of all solutions to the homogeneous system $A\mathbf{x} = \mathbf{0}$ is spanned by the two linearly independent vectors $[1, 1, 0, 0, 0]^T$ and $[0, 0, 1, 1, 0]^T$. What is the rank of the matrix $A$?" answer="3" hint="The set of solutions to $A\mathbf{x}=\mathbf{0}$ is the null space of $A$. The dimension of this space (the nullity) is given by the number of linearly independent vectors that span it. Apply the Rank-Nullity Theorem." solution="
The problem states that the solution space of the homogeneous system $A\mathbf{x} = \mathbf{0}$ is spanned by two linearly independent vectors. This solution space is, by definition, the null space of the matrix $A$.

The dimension of the null space is called the nullity of $A$, denoted as $\operatorname{nullity}(A)$. The dimension is equal to the number of linearly independent vectors in any basis for that space. Since the two given spanning vectors are linearly independent, they form a basis for the null space.
Therefore,

The matrix $A$ is a $4 \times 5$ matrix, which means it has $n=5$ columns.

We now apply the Rank-Nullity Theorem, which states that for any $m \times n$ matrix:

Substituting the known values:

Solving for the rank of $A$:

The rank of the matrix $A$ is 3.
"
:::

:::question type="MCQ" question="Let $A$ be an $m \times n$ matrix with rank $r$, where $r < n$. The number of linearly independent solutions to the homogeneous system of equations $A\mathbf{x} = \mathbf{0}$ is:" options=["$r$","$n-r$","$n$","$m-r$"] answer="B" hint="The number of linearly independent solutions to a homogeneous system corresponds to the dimension of its null space. Recall the fundamental theorem that connects rank, nullity, and the number of columns of a matrix." solution="
The question asks for the number of linearly independent solutions to the homogeneous system $A\mathbf{x} = \mathbf{0}$. This is equivalent to asking for the dimension of the null space of the matrix $A$, which is defined as the nullity of $A$.

We are given:

• The matrix $A$ has dimensions $m \times n$, so the number of columns is $n$.


• The rank of the matrix is $\operatorname{rank}(A) = r$.


• It is also given that $r < n$.

The Rank-Nullity Theorem provides the relationship between the rank, nullity, and the number of columns ($n$) of a matrix:

We can rearrange this equation to solve for the nullity:

Substituting the given rank $r$:

The nullity represents the dimension of the solution space for the homogeneous system, which corresponds to the number of free variables, and thus the number of linearly independent solution vectors.
Since $r < n$, the nullity $n-r$ is at least 1, confirming the existence of non-trivial solutions.
Therefore, the number of linearly independent solutions is $n-r$.
"
:::

---

What's Next?