Row Reduced Canonical Form

MEDIUM20 pts

In linear algebra, the Row Reduced Canonical Form (RRCF), also known as the Row Reduced Echelon Form, is a standardized representation of a matrix obtained through Gaussian-Jordan elimination. This transformation is fundamental for solving systems of linear equations, computing matrix ranks, finding null spaces, and understanding the structure of linear mappings.

A matrix is in Row Reduced Canonical Form when it satisfies the following properties:

Leading Ones (Pivots): Each non-zero row has its first non-zero entry equal to 1, called a pivot or leading entry
Zero Columns Above and Below Pivots: In any column containing a pivot, all other entries (both above and below the pivot) are 0
Staircase Pattern: The pivot in each succeeding row appears to the right of the pivot in the preceding row
Zero Rows at Bottom: Any rows consisting entirely of zeros are placed at the bottom of the matrix

Key Observations:

If a column contains a pivot element (leading 1), all other entries in that column must be zero
Some rows may reduce entirely to zeros during elimination
The number of pivot positions equals the rank of the matrix
The algorithm transforms the matrix using only elementary row operations: swapping rows, multiplying a row by a non-zero scalar, and adding a multiple of one row to another

Your Task: Write a Python function that converts any given matrix into its Row Reduced Canonical Form. The function should correctly handle:

Rectangular matrices (both wide and tall)
Matrices with linearly dependent rows
Matrices where pivot positions may not be on the main diagonal
Matrices that may contain zero rows after reduction

Example

Input

matrix = [[1, 2, -1, -4], [2, 3, -1, -11], [-2, 0, -3, 22]]

Output

[[1.0, 0.0, 0.0, -8.0], [0.0, 1.0, 0.0, 1.0], [0.0, 0.0, 1.0, -2.0]]

Explanation

Starting with a 3×4 matrix, we apply Gaussian-Jordan elimination:

• Step 1: Use row 1 as the first pivot row (already has leading 1). • Step 2: Eliminate entries below the first pivot: R2 ← R2 - 2×R1, R3 ← R3 + 2×R1. • Step 3: Scale row 2 to create the second pivot (leading 1). • Step 4: Eliminate entries above and below the second pivot. • Step 5: Continue with row 3 to create the third pivot and back-substitute.

The final RRCF has leading 1s in columns 1, 2, and 3, with all other entries in these columns being 0. The last column represents the solution constants if this were an augmented matrix for a system of equations (x = -8, y = 1, z = -2).

Example

Input

matrix = [[1, 2, 3], [4, 5, 6]]

Output

[[1.0, 0.0, -1.0], [0.0, 1.0, 2.0]]

Explanation

For this 2×3 matrix:

• Pivot 1: The (1,1) entry is already 1. • Eliminate below: R2 ← R2 - 4×R1 yields [0, -3, -6]. • Pivot 2: Scale R2 by (-1/3) to get leading 1: [0, 1, 2]. • Eliminate above: R1 ← R1 - 2×R2 yields [1, 0, -1].

The matrix has rank 2, with pivots in columns 1 and 2. Column 3 is a free variable column in the context of solving homogeneous systems.

Example

Input

matrix = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]

Output

[[1.0, 0.0, 0.0], [0.0, 1.0, 0.0], [0.0, 0.0, 1.0]]

Explanation

The 3×3 identity matrix is already in Row Reduced Canonical Form! Each row has exactly one leading 1, the pivots form a perfect diagonal staircase, and all non-pivot entries are 0. This is the "maximally reduced" form—no further simplification is possible. The identity matrix is its own RRCF, demonstrating that the algorithm correctly recognizes matrices that are already in canonical form.

Accepted0/0·0% Acceptance

Constraints

1 ≤ n ≤ 100 (number of rows)
1 ≤ m ≤ 100 (number of columns)
-10⁶ ≤ matrix[i][j] ≤ 10⁶
The matrix will contain at least one element
All rows will have the same length (valid matrix format)
Output values should be accurate to at least 6 decimal places

Code

Visualizer

Solutions

14px

Test Cases3

Results

Submissions

matrix =

[[1,2,-1,-4],[2,3,-1,-11],[-2,0,-3,22]]

Row Reduced Canonical Form

Hints

Row Reduced Canonical Form

Hints