0/318

00:00:00

Description

Editorial

Column Space Basis Extraction

MEDIUM20 pts

The column space of a matrix, also known as its image or range, is one of the four fundamental subspaces in linear algebra. It represents the set of all possible output vectors that can be produced when the matrix acts as a linear transformation—in other words, all vectors that can be expressed as linear combinations of the matrix's columns.

The Mathematical Foundation

Given a matrix A with dimensions m × n (m rows, n columns), the column space is defined as:

$$\text{Col}(A) = { A\mathbf{x} : \mathbf{x} \in \mathbb{R}^n } = \text{span}{\mathbf{a}_1, \mathbf{a}_2, \ldots, \mathbf{a}_n}$$

where a₁, a₂, ..., aₙ are the column vectors of matrix A. However, not all columns may be linearly independent—some columns might be expressible as combinations of others. The dimension of the column space equals the rank of the matrix.

Finding the Basis

To find a basis for the column space, we need to identify which columns of the original matrix are linearly independent. The most reliable method involves:

Row Reduction: Transform the matrix to Row Echelon Form (REF) using Gaussian elimination
Pivot Identification: Locate the pivot positions (the first non-zero entry in each row)
Column Extraction: The columns of the original matrix corresponding to pivot positions form a basis

Critical Note: While we use the row-reduced form to identify pivot positions, the actual basis vectors must come from the original matrix, not the reduced form. This preserves the structure of the original column space.

Your Task

Implement a function column_space_basis(A) that:

Takes a matrix A as input
Computes the row echelon form to identify pivot columns
Returns the corresponding columns from the original matrix as basis vectors
The output should be a matrix where each column is a basis vector

The returned matrix should contain the linearly independent columns from the original matrix that span its column space.

Example

Input

A = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

Output

[[1, 2], [4, 5], [7, 8]]

Explanation

This 3×3 matrix has rank 2, meaning only 2 columns are linearly independent. When we perform row reduction:

After Gaussian elimination, the row echelon form reveals that the first two columns contain pivots
The third column is a linear combination of the first two (specifically, col₃ = 2·col₂ - col₁)
Therefore, columns 1 and 2 from the original matrix form the basis: [1, 4, 7] and [2, 5, 8]

The output matrix [[1, 2], [4, 5], [7, 8]] represents these two basis vectors as columns, spanning the 2-dimensional column space.

Example

Input

A = [[1, 0], [0, 1]]

Output

[[1, 0], [0, 1]]

Explanation

This is the 2×2 identity matrix, which has full rank (rank = 2). Both columns are linearly independent—neither can be expressed as a scalar multiple of the other.

The row echelon form is already the matrix itself, with pivots in both column positions. Therefore, the entire original matrix forms the basis for its column space, which spans all of ℝ².

The output is the complete original matrix: [[1, 0], [0, 1]].

Example

Input

A = [[1, 2, 0], [0, 1, 1], [1, 0, 1]]

Output

[[1, 2, 0], [0, 1, 1], [1, 0, 1]]

Explanation

This 3×3 matrix has full column rank (rank = 3), meaning all three columns are linearly independent. Row reduction confirms that each column position contains a pivot.

Since no column can be written as a linear combination of the others, all three columns are needed to form the basis. The column space equals the entire 3-dimensional space ℝ³.

The output includes all columns from the original matrix: [[1, 2, 0], [0, 1, 1], [1, 0, 1]].

Accepted0/0·0% Acceptance

Constraints

1 ≤ m ≤ 100 (number of rows)
1 ≤ n ≤ 100 (number of columns)
-10⁶ ≤ A[i][j] ≤ 10⁶ for all matrix elements
The matrix will always contain at least one non-zero element
All rows have the same number of columns (valid matrix format)
The function should handle both square and rectangular matrices

Code

Visualizer

Solutions

14px

Test Cases3

Results

Submissions

A =

[[1,2,3],[4,5,6],[7,8,9]]

The Mathematical Foundation

Given a matrix A with dimensions m × n (m rows, n columns), the column space is defined as:

$$\text{Col}(A) = { A\mathbf{x} : \mathbf{x} \in \mathbb{R}^n } = \text{span}{\mathbf{a}_1, \mathbf{a}_2, \ldots, \mathbf{a}_n}$$

Finding the Basis

To find a basis for the column space, we need to identify which columns of the original matrix are linearly independent. The most reliable method involves:

Row Reduction: Transform the matrix to Row Echelon Form (REF) using Gaussian elimination

Pivot Identification: Locate the pivot positions (the first non-zero entry in each row)

Column Extraction: The columns of the original matrix corresponding to pivot positions form a basis

Your Task

Implement a function column_space_basis(A) that:

Takes a matrix A as input

Computes the row echelon form to identify pivot columns

Returns the corresponding columns from the original matrix as basis vectors

The output should be a matrix where each column is a basis vector

The returned matrix should contain the linearly independent columns from the original matrix that span its column space.

Column Space Basis Extraction

The Mathematical Foundation

Finding the Basis

Your Task

Hints

Column Space Basis Extraction

The Mathematical Foundation

Finding the Basis

Your Task

Hints