Extended Echelon Form

Overview

Reducing a matrix to reduced row-echelon form answers many questions but discards one important thing: how you got there. Each row of the result is a linear combination of the original rows, yet the coefficients of those combinations vanish once the reduction is complete. Extended echelon form preserves them by attaching an identity block to the right of the matrix and applying every row operation to the enlarged array.

The mechanism is the same one used to invert a nonsingular matrix by reducing $[\, A \mid I_n \,]$ , and the generalisation is exact. Here $A$ need be neither square nor nonsingular. What emerges in the appended block is a nonsingular matrix $J$ satisfying $JA = B$ , where $B$ is the reduced form of $A$ . When $A$ happens to be square and nonsingular, $B$ is the identity and $J$ is the inverse; in every other case $J$ is still nonsingular and still a complete record of the reduction.

The value of the construction comes from partitioning $N = [\, B \mid J \,]$ along the boundary set by the rank. Let $r$ be the number of non-zero rows of $B$ . Then $C$ is the top $r$ rows of $B$ , $K$ is the top $r$ rows of $J$ , and $L$ is the bottom $m - r$ rows of $J$ . Both $C$ and $L$ are already in reduced row-echelon form with no zero rows, so both are immediately ready for analysis without further reduction.

That readiness is the point. Two small, clean matrices carry the structural content of the original: $C$ governs the unknowns and $L$ governs the equations. From them the null space, row space, column space and left null space all follow with nothing more than standard basis extractions. The extended form is therefore best understood not as another canonical form but as a single computation that pays for four separate ones.

Definition

EEF

Let $A$ be an $m \times n$ matrix. Adjoin the $m \times m$ identity matrix to form the $m \times (n + m)$ matrix $M = [\, A \mid I_m \,]$ , and reduce $M$ to reduced row-echelon form. The result $N$ is the extended reduced row-echelon form of $A$ .
Write $B$ for the first $n$ columns of $N$ and $J$ for the last $m$ columns. Let $r$ be the number of non-zero rows of $B$ . Then:

$C$ is the $r \times n$ matrix formed from the non-zero rows of $B$ ;
$K$ is the $r \times m$ matrix formed from the first $r$ rows of $J$ ;
$L$ is the $(m - r) \times m$ matrix formed from the last $m - r$ rows of $J$ .

Because the reduced row-echelon form of $M$ is unique, all five submatrices are determined by $A$ alone — no dependence on the sequence of row operations chosen.

Properties of Extended Echelon Form

PEEF

Let $A$ be an $m \times n$ matrix with extended echelon form $N$ . Then:

$J$ is nonsingular.
$B = JA$ .
For $\vec{x} \in \mathbb{C}^n$ and $\vec{y} \in \mathbb{C}^m$ , $A\vec{x} = \vec{y}$ if and only if $B\vec{x} = J\vec{y}$ .
$C$ is in reduced row-echelon form, has no zero rows, and has $r$ pivot columns.
$L$ is in reduced row-echelon form, has no zero rows, and has $m - r$ pivot columns.

Block structure of $N$

BSN

The five submatrices assemble into a two-by-two block picture, with a zero block occupying the bottom-left corner because the last $m - r$ rows of $B$ are zero rows: $N = \begin{bmatrix} C & K \\ 0 & L \end{bmatrix}$ . Reading this layout is the fastest route to remembering which submatrix sits where.

Concepts

Why $J$ is nonsingular

The appended block starts as $I_m$ and is transformed by exactly the same sequence of row operations that reduces $A$ , so $J$ and $I_m$ are row-equivalent. Row-equivalent matrices have identical null spaces, and the identity matrix has only the trivial null space, so $\mathcal{N}(J) = \{\vec{0}\}$ and $J$ is nonsingular. Nothing about $A$ enters this argument, which is why the conclusion holds even when $A$ is rectangular or rank-deficient.

Why $B = JA$

Row operations commute with matrix multiplication on the right. If $F$ reduces to $G$ under a sequence of operations, then applying the same sequence to the product $F H$ produces $G H$ . Begin from the trivial identity $AI_n = I_mA$ and apply the reduction that converts $M$ to $N$ : the left side sees $A$ converted to $B$ , giving $BI_n$ ; the right side sees $I_m$ converted to $J$ , giving $J A$ . Simplifying the left side yields $B = JA$ directly.

The translated system

The third property is the operationally significant one. It says the systems $A\vec{x} = \vec{y}$ and $B\vec{x} = J\vec{y}$ have identical solution sets. The forward direction follows by multiplying through by $J$ ; the reverse follows by multiplying by $J^{-1}$ , which exists because $J$ is nonsingular. Concretely: reducing the augmented matrix $[\, A \mid \vec{y} \,]$ always produces $[\, B \mid J\vec{y} \,]$ . The matrix $J$ is precisely the operator that applies the accumulated row operations to any vector of constants.

Why $C$ and $L$ are already reduced

Any contiguous block of rows taken from a matrix in reduced row-echelon form is itself in reduced row-echelon form. $C$ consists of the first $r$ rows of $N$ with the last $m$ entries removed, and deleting trailing columns cannot break the echelon conditions, so $C$ is reduced with $r$ leading ones. $L$ consists of the last $m - r$ rows of $N$ with the first $n$ entries removed; those removed entries are all zero, being the zero rows of $B$ , so again the conditions survive. Neither $L$ nor $C$ can have a zero row: a zero row in $L$ would make a whole row of the nonsingular matrix $J$ zero.

Generalising the inverse

Suppose $A$ is square and nonsingular. Then its reduced form is the identity, so $B = I_n$ and the identity $JA = B$ becomes $JA = I_n$ : the appended block is a left inverse of $A$ , and for a square nonsingular matrix that is the inverse. The classical augmented-reduction algorithm for computing $A^{-1}$ is therefore the special case $m = n = r$ of this construction. In that case $L$ has no rows, reflecting the absence of any consistency condition on the right-hand side.

The two halves carry different information

The split at row $r$ separates two distinct kinds of structure. The top block, $[\, C \mid K \,]$ , describes the unknowns: $C$ holds the surviving equations after redundancy is removed, and $K$ maps a right-hand side into the constants of those equations. The bottom block, $[\, 0 \mid L \,]$ , describes the equations: the zeros record that $m - r$ combinations of the original rows vanish identically, and $L$ holds the scalars producing them. One block solves; the other tests solvability.

Constructing the extended echelon form

Augment with the identityForm

M = [\, A \mid I_m \,]

, an

m \times (n + m)

array. The identity block must have size

m

, matching the row count of

A

, not the column count.

Reduce the left blockApply row operations to the full width of the array until the first

n

columns are in reduced row-echelon form. Count the non-zero rows to obtain

r

Continue into the appended blockPlace leading ones in the final

m - r

rows and clear their columns above. This standardises the result so that

N

is the unique reduced form of

M

PartitionSplit

N

into

B

(first

n

columns) and

J

(last

m

columns), then take

C

and

K

from the top

r

rows and

L

from the bottom

m - r

rows.

VerifyCheck

JA = B

by direct multiplication, and confirm that

C

has

r

pivot columns and

L

has

m - r

, both with no zero rows.

Equations

The construction

EQ-EEF-01

M = [A ∣ I_{m}] \overset{RREF}{\to} N = [B ∣ J]

The identity block has size equal to the number of rows of $A$ , so the array is $m \times (n + m)$ regardless of the shape of $A$ .

Block partition of $N$

EQ-EEF-02

N = [\begin{matrix} C & K \\ 0 & L \end{matrix}]

$C$ is $r \times n$ , $K$ is $r \times m$ , $L$ is $(m-r) \times m$ , and the zero block is $(m-r) \times n$ , comprising the zero rows of $B$ .

The transforming identity

EQ-EEF-03

J A = B, J nonsingular

$J$ records the cumulative effect of every row operation. Its nonsingularity follows from being row-equivalent to $I_m$ .

System translation

EQ-EEF-04

A \vec{x} = \vec{y} \Leftrightarrow B \vec{x} = J \vec{y}

Equivalently, reducing $[\, A \mid \vec{y} \,]$ always yields $[\, B \mid J\vec{y} \,]$ . The forward direction multiplies by $J$ ; the reverse by $J^{-1}$ .

Consistency in terms of $L$

EQ-EEF-05

A \vec{x} = \vec{y} consistent \Leftrightarrow L \vec{y} = \vec{0}

The last $m - r$ entries of $J\vec{y}$ must vanish for the translated system to be consistent, and those entries are exactly $L\vec{y}$ .

Reduction to the inverse

EQ-EEF-06

A \in M_{n n} nonsingular \Rightarrow B = I_{n}, J = A^{- 1}, L empty

The classical augmented-reduction algorithm for the inverse is the special case $m = n = r$ of the extended echelon form.

Pivot counts of the two reduced blocks

EQ-EEF-07

rank (C) = r, rank (L) = m - r

Both blocks are in reduced form with no zero rows, so each has full row rank. Their ranks sum to $m$ .

Variable Definitions

Symbols used on this page
Symbol	Name	Meaning	Domain / type
$A$	Input matrix	The $m \times n$ matrix being analysed	m x n matrix over C
$M$	Augmented array	$[\, A \mid I_m \,]$ , the input to the reduction	m x (n+m) matrix
$N$	Extended echelon form	The reduced row-echelon form of $M$ , partitioned as $[\, B \mid J \,]$	m x (n+m) matrix
$B$	Reduced matrix	First $n$ columns of $N$ ; the reduced row-echelon form of $A$ , with $m - r$ zero rows	m x n matrix
$J$	Transforming matrix	Last $m$ columns of $N$ ; nonsingular, with $JA = B$	m x m nonsingular matrix
$Top-left block$	Top-left block	The $r$ non-zero rows of $B$ ; reduced, no zero rows, $r$ pivot columns	r x n matrix
$Top-right block$	Top-right block	First $r$ rows of $J$ ; maps a right-hand side to the constants of the surviving equations	r x m matrix
$Bottom-right block$	Bottom-right block	Last $m - r$ rows of $J$ ; reduced, no zero rows, encodes the consistency conditions	(m-r) x m matrix
$r$	Rank	Number of non-zero rows of $B$ ; sets the partition boundary	0 to min(m,n)

Worked Numerical Example

Problem statement

A four-node network is driven by three supply settings. Build the extended echelon form of the 4 by 3 map from settings to nodal demands, identify all five submatrices, verify the defining properties, and use the translated system to solve for a specific achievable demand without ever forming an ordinary augmented matrix.

Augment with the identity
With $m = 4$ and $n = 3$ , adjoin $I_4$ to the right of $A$ to form a $4 \times 7$ array. The identity block matches the row count, which is what makes the appended block a record of row operations.
$M = [\begin{matrix} 1 & 2 & 1 & 1 & 0 & 0 & 0 \\ 2 & 3 & 1 & 0 & 1 & 0 & 0 \\ 3 & 5 & 2 & 0 & 0 & 1 & 0 \\ 5 & 8 & 3 & 0 & 0 & 0 & 1 \end{matrix}]$
Reduce the whole array
Apply row operations across the full width. The left block reaches reduced form with two non-zero rows, so $r = 2$ ; the reduction then continues so that the final two rows acquire leading ones inside the appended block and those columns are cleared above.
$N = [\begin{matrix} 1 & 0 & - 1 & 0 & 0 & - 8 & 5 \\ 0 & 1 & 1 & 0 & 0 & 5 & - 3 \\ 0 & 0 & 0 & 1 & 0 & - 2 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & - 1 \end{matrix}]$
Identify the five submatrices
Split at column $n = 3$ to get $B$ and $J$ , then split at row $r = 2$ to get $C$ , $K$ and $L$ . The bottom-left block is zero, as it must be, since those are the zero rows of $B$ .
$C = [\begin{matrix} 1 & 0 & - 1 \\ 0 & 1 & 1 \end{matrix}], K = [\begin{matrix} 0 & 0 & - 8 & 5 \\ 0 & 0 & 5 & - 3 \end{matrix}], L = [\begin{matrix} 1 & 0 & - 2 & 1 \\ 0 & 1 & 1 & - 1 \end{matrix}]$
Verify $JA = B$
Multiply the appended block by the original matrix. Row 3 of $J$ is $(1, 0, -2, 1)$ , and applying it to the columns of $A$ gives $1 - 6 + 5 = 0$ , $2 - 10 + 8 = 0$ and $1 - 4 + 3 = 0$ — a zero row, exactly as $B$ requires. The same check on rows 1, 2 and 4 completes the verification.
$Verify $JA = B$$
Confirm $J$ is nonsingular
Rows 3 and 4 of $J$ hold leading ones in columns 1 and 2 of the block, and rows 1 and 2 hold zeros there. Reducing $J$ alone returns $I_4$ , so $J$ is nonsingular and the translation between systems is reversible in both directions.
Test a demand vector using $L$
Take $\vec{y} = (3,\, 1,\, 4,\, 5)$ . Then $L\vec{y}$ has entries $3 - 8 + 5 = 0$ and $1 + 4 - 5 = 0$ , so $L\vec{y} = \vec{0}$ and the system is consistent. This is the whole consistency test: two inner products, no elimination.
Solve via the translated system
Compute $J\vec{y} = (-7,\, 5,\, 0,\, 0)$ , whose first $r = 2$ entries are $K\vec{y}$ . Solving $B\vec{x} = J\vec{y}$ means solving $x_1 - x_3 = -7$ and $x_2 + x_3 = 5$ , with $x_3$ free. Setting $x_3 = 0$ gives $\vec{x} = (-7,\, 5,\, 0)$ .
$\vec{x} = [\begin{matrix} - 7 + x_{3} \\ 5 - x_{3} \\ x_{3} \end{matrix}], x_{3} free$
Check against the original system
Substituting $\vec{x} = (-7, 5, 0)$ into $A$ gives $-7 + 10 = 3$ , $-14 + 15 = 1$ , $-21 + 25 = 4$ and $-35 + 40 = 5$ , reproducing $\vec{y}$ exactly. The translated system delivered the correct solution set without the original augmented matrix ever being reduced.

Result

One reduction of a $4 \times 7$ array yields the rank $r = 2$ , a nonsingular transformation $J$ with $JA = B$ , a two-row consistency test $L$ , and a mechanism for solving $A\vec{x} = \vec{y}$ for any right-hand side at the cost of one matrix-vector product plus a back-substitution on a $2 \times 3$ system. Where the same coefficient matrix is queried repeatedly, that up-front cost is amortised immediately.

Applications & Industry Use

Embedded control

Precomputed solvers for a fixed plant matrix

A controller whose plant model is fixed at design time can store $J$ , $C$ and $L$ in firmware. At runtime, screening a demand vector costs $m - r$ inner products and solving costs one matrix-vector product with $K$ plus a triangular back-substitution, all with deterministic timing and no dynamic allocation — properties an online elimination cannot offer.

Computer algebra systems

Certified structural computations

The identity $JA = B$ is a machine-checkable certificate that a reported reduced form is genuinely row-equivalent to the input. Symbolic systems can return $J$ alongside the reduced form so that a downstream consumer verifies the claim with a single multiplication instead of trusting the reduction.

Structural analysis

Equilibrium and mechanism detection in one pass

Applied to an equilibrium matrix, the construction yields the achievable load space through $L$ and the self-stress states through $C$ simultaneously. A structure's degree of static indeterminacy and its degree of kinematic indeterminacy are read from the same reduction rather than from two separate analyses.

Network and flow modelling

Conservation checks alongside flow solutions

For a node-arc incidence matrix, $L$ encodes the conservation identities that any feasible supply vector must satisfy, while $C$ and $K$ provide the machinery to compute a feasible flow. Model builders get a validity check on the input data and a solver for it from a single computation.

Cryptography and coding

Systematic form with recorded transformation

Bringing a generator matrix to systematic form requires row operations, and decoders often need the transformation itself to map back into the original coordinates. The appended block supplies exactly that transformation, and its nonsingularity guarantees the mapping is invertible.

Model-based diagnostics

Residual generator synthesis

The rows of $L$ are precisely the combinations of model equations that cancel, so they define residual generators independent of the unknown state. Deriving them from the extended form gives an automated route from a structural model to a deployable diagnostic test set.

Design Considerations

Size the identity block by rows, not columns

The appended block is $I_m$ , matching the number of rows of $A$ . Using $I_n$ is a common slip that produces an array of the wrong shape for rectangular matrices and silently produces a meaningless $J$ for square ones only by coincidence. The array width is always $n + m$ .

Carry the reduction to completion or lose uniqueness

Stopping once the left block is reduced leaves the appended block un-normalised, so the resulting $L$ depends on the operation order and cannot be compared across computations. Continuing until the whole array is in reduced form makes $N$ unique, which matters whenever the result is recorded, published or regression-tested.

The cost is real for square matrices

Reducing an $m \times (n + m)$ array rather than $m \times n$ roughly doubles the arithmetic for a square input. That cost buys $J$ , $L$ and material for all four fundamental subsets. If the deliverable is a single solve or a rank figure, an ordinary elimination or an LU factorisation is the better choice.

$J$ is dense even when $A$ is sparse

The transforming matrix accumulates the entire history of the reduction and is generally dense regardless of the sparsity of $A$ . For large sparse problems, forming $J$ explicitly can exceed available memory by orders of magnitude. Sparse workflows should extract the specific rows of $L$ that are needed rather than materialise the whole block.

Treat $J$ as a left inverse, not an inverse

The relation is $JA = B$ with $B = I_n$ only in the nonsingular square case. For rectangular $A$ there is no claim that $A J$ is anything in particular, and writing $J$ as $A^{-1}$ outside the square nonsingular case is a category error that will produce wrong results as soon as the product is taken in the other order.

Numerical use requires a rank tolerance

The partition boundary is $r$ , which in floating point is a threshold decision. An error of one in the computed rank moves a row between $K$ and $L$ , changing both the consistency test and the solution machinery. Where the input is measured data, derive the equivalent structure from an SVD with a stated tolerance rather than from an exact-arithmetic partition.

Standards & Codes

Notation, interchange and numerical standards that govern how this material is written down, stored and computed in production systems.

Applicable standards, conventions and reference implementations
Reference	Title	Relevance to this topic
`ISO 80000-2`	Quantities and units — Part 2: Mathematics	Fixes the partitioned-matrix notation, the identity matrix symbol $I_m$ and the block delimiters used to present $[\, A \mid I_m \,]$ and its two-by-two block reduction.
`LAPACK / BLAS reference`	Linear Algebra PACKage reference implementation	LAPACK exposes factorisations rather than augmented reductions; the closest production analogues of $J$ are the accumulated transformations returned by `xGETRF` and `xGEQRF`, which are stored in factored form precisely because the explicit product is dense.
`IEEE 754-2019`	IEEE Standard for Floating-Point Arithmetic	Determines the accumulated rounding in $J$ , which grows with the number of operations recorded and makes the identity $JA = B$ hold only to within a tolerance in practice.
`ISO/IEC 14882`	Programming languages — C++	Fixes the row-major storage and aliasing rules that govern how an augmented array is laid out in memory and whether the two blocks can share an allocation safely.
`ISO/IEC 40314`	Mathematical Markup Language (MathML) Version 3.0	Encodes the partitioned arrays with visible block dividers as semantic markup, so the boundary between $A$ and the identity block is conveyed structurally rather than visually.

Material Selection

For a mathematical topic, "material" is the numeric representation: the scalar field, storage format and precision the computation is built from.

Representation and precision selection
Representation	Select when	Trade-off
Exact rational arithmetic	Deriving $J$ , $C$ and $L$ for a symbolic or small integer matrix where the identity $JA = B$ must hold exactly.	Guarantees an exact partition boundary and a verifiable certificate, but the appended block accumulates the full operation history and its entries can grow rapidly.
Arbitrary-precision integers with denominator clearing	Integer input where $L$ should be reported with integer coefficients, as for conservation or closure relations.	Keeps the conditions readable and physically meaningful; requires an explicit normalisation convention so that results are comparable between computations.
IEEE 754 binary64	Moderate dense matrices where the structure is known and only the numeric transformation is required.	Fast, but rounding accumulates in $J$ across every recorded operation, so $J A$ matches $B$ only to a tolerance and the partition boundary must be chosen with a rank threshold.
Orthogonal accumulation (QR with stored reflectors)	A numerically stable analogue of $J$ is needed for floating-point data.	Householder reflectors accumulate an orthogonal transformation with no growth in rounding error, but the result is an orthogonal triangularisation rather than a reduced echelon form and loses the zero-one pattern.
Finite field arithmetic	Coding applications where systematic form and its recorded transformation are both required.	Exact and free of growth, with the appended block giving the invertible change of coordinates directly; restricted to the algebraic setting of the code.
Factored storage instead of explicit $J$	Large problems where the dense transformation cannot be held in memory.	Storing the operation sequence and applying it on demand keeps memory proportional to the operation count, at the cost of re-application time for each right-hand side.

Manufacturing Notes

Implementation notes — how the result is actually produced by hand, by algorithm and by library, including cost and numerical behaviour.

Operation count

Reducing the $m \times (n + m)$ array costs on the order of $m(n + m)r$ multiply-adds against $m n r$ for reducing $A$ alone. For a square matrix that is close to a factor of two; for a wide matrix with $n \gg m$ the overhead is proportionally smaller. The additional work is exactly the cost of transforming the identity block.

Performing the reduction by hand

Draw the divider between the blocks and apply every operation across it without exception. Complete the left block first, count the zero rows to fix $r$ , then normalise the trailing rows within the appended block. Working the appended block early is a common source of confusion, because the pivot positions there are only determined once $r$ is known.

Verification technique

Multiply $J$ by $A$ and compare with $B$ entry for entry; this single check validates the entire reduction. Confirm independently that $J$ reduces to $I_m$ , that $C$ has exactly $r$ leading ones, and that $L$ has exactly $m - r$ leading ones with no zero rows. Any failure localises the error to a specific block.

Library behaviour

No mainstream numerical library implements extended echelon form directly. In SymPy it is built by horizontally stacking the matrix with eye(m) and calling rref(), then slicing the result. Numerical work substitutes factorisations: LU with pivoting gives a factored transformation, and SVD gives orthonormal bases playing the roles of $C$ and $L$ with well-defined conditioning.

Rounding accumulation in $J$

Because $J$ records every operation, its entries accumulate rounding proportional to the length of the reduction and can have a much larger condition number than $A$ itself. Where the transformation must be applied to many right-hand sides in floating point, an orthogonal accumulation is preferable: orthogonal transformations do not amplify error, whereas elimination-derived transformations can.

Failure Modes & Common Mistakes

Failure modes, root causes and prevention
Failure mode / mistake	Impact	Root cause	Prevention & detection
Augmenting with $I_n$ instead of $I_m$	high	Matching the identity block to the column count rather than the row count of $A$ .	The block must be $m \times m$ so that it can record row operations. Check that the augmented array has width $n + m$ before reducing.
Omitting the appended block on an operation	high	Applying a row operation to the left block only, so $J$ no longer records the true transformation.	Verify $JA = B$ by multiplication before extracting any submatrix; the check fails immediately if any operation was skipped.
Halting once the left block is reduced	medium	Treating the left block as the objective and leaving the appended block un-normalised, so the result is not canonical.	Continue until the trailing rows have leading ones in the appended block and those columns are cleared above.
Swapping $K$ and $L$	medium	Taking the first $m - r$ rows of $J$ as $L$ rather than the last.	$L$ is the block aligned with the zero rows of $B$ . Confirm with $L\vec{A}_j = \vec{0}$ for every column of $A$ ; $K$ does not satisfy this.
Treating $J$ as an inverse of $A$	high	Generalising $JA = B$ into a claim about $A J$ , which holds only when $A$ is square and nonsingular.	Use $J$ only in the left-multiplied form. For rectangular $A$ , $A J$ is not even conformable unless $m = n$ .
Mistaking the partition boundary	medium	Setting $r$ from the number of columns or from the smaller dimension rather than from the count of non-zero rows of $B$ .	Count non-zero rows of the reduced left block explicitly and confirm that $C$ and $L$ have $r$ and $m - r$ rows respectively.
Materialising $J$ for a large sparse matrix	medium	Applying the construction to a sparse problem, where the dense transforming matrix exhausts memory.	Extract only the required rows of $L$ , or use a sparse factorisation with the transformation held in factored form.
Exact rank assumption on floating-point data	high	Partitioning at a rank determined by exact-zero pivot tests on rounded entries.	Determine rank from an SVD with a documented tolerance and report the singular-value gap that justifies the partition.

FAQs

How does this differ from ordinary reduced row-echelon form?

It is the same reduction applied to a wider array. The extra columns start as an identity matrix and end as a nonsingular matrix $J$ satisfying $JA = B$ , so the construction preserves the record of how the reduction was performed. Ordinary reduction discards that information.

Why does the appended block have to be square of size

m

Because it records row operations, and there are $m$ rows. Each row of the final block gives the coefficients expressing the corresponding row of $B$ as a combination of the rows of $A$ . An identity of size $n$ would not be conformable for that role unless $A$ happened to be square.

J

the inverse of

A

Only when $A$ is square and nonsingular, in which case $B = I_n$ and $JA = I_n$ makes $J$ the inverse. In general $J$ is a nonsingular matrix satisfying $JA = B$ and should be treated as a left-acting transformation. Nothing is claimed about $A J$ , which need not even be defined.

What are

C

and

L

for?

$C$ holds the surviving equations after redundancy is removed and governs the unknowns; from it the null space and row space of $A$ follow directly. $L$ holds the combinations of equations that vanish and governs solvability; from it the column space and left null space follow. Both are already in reduced form, so no further reduction is needed.

Why must I continue reducing after the left block is finished?

To make the result unique. Different operation orders leave the appended block in different states, so $L$ would not be canonical and two computations could not be compared. Reducing the entire array makes $N$ the unique reduced row-echelon form of $M$ , and hence determined by $A$ alone.

What does the third property actually buy me?

It says that $A\vec{x} = \vec{y}$ and $B\vec{x} = J\vec{y}$ have the same solutions. Once $J$ and $B$ are computed, solving for any new right-hand side costs one matrix-vector product and a back-substitution on an $r \times n$ reduced system, instead of a fresh elimination on the full augmented matrix.

Is this practical for large matrices?

Rarely in the explicit form. The transforming matrix is dense even when $A$ is sparse, and the arithmetic roughly doubles for square inputs. Its value is conceptual and small-scale: it explains where consistency conditions come from and it delivers all four fundamental subsets from one computation. Production code uses factorisations that keep the transformation in factored form.

References

Beezer, R. A. A First Course in Linear Algebra, Version 0.70. University of Puget Sound, 2006. Section FS, Subsection EEF. Licensed under the GNU Free Documentation License v1.2.
ISO 80000-2:2019, Quantities and units — Part 2: Mathematics. International Organization for Standardization.
Golub, G. H. and Van Loan, C. F. Matrix Computations, 4th edition. Johns Hopkins University Press, 2013.
Higham, N. J. Accuracy and Stability of Numerical Algorithms, 2nd edition. Society for Industrial and Applied Mathematics, 2002.
Anderson, E. et al. LAPACK Users' Guide, 3rd edition. Society for Industrial and Applied Mathematics, 1999.

AI Suggested Questions

Work through the extended echelon form of a 5x3 matrix of rank 2 and identify all five submatrices with their exact dimensions.
Prove that row operations commute with matrix multiplication on the right, and show how that argument yields the identity JA = B.
Compare the condition number of the transforming matrix J against that of the original matrix for an ill-conditioned example.
Show explicitly how the extended echelon form reduces to the classical augmented-reduction algorithm for a matrix inverse when the input is square and nonsingular.
Why must L have no zero rows, and what would a zero row in L imply about the nonsingularity of J?
Design a firmware routine that stores C, K and L for a fixed plant matrix and solves for arbitrary right-hand sides in deterministic time.

Related Calculators

Extended Echelon Form Calculator

Reduce $[\, A \mid I_m \,]$ and return $B$ , $C$ , $J$ , $K$ and $L$ with a verification of $JA = B$ .

RREF Calculator

Reduce any matrix to reduced row-echelon form with a full audit trail of the row operations applied.

Matrix Inverse Calculator

Invert a square matrix by augmented reduction, the nonsingular special case of the extended echelon form.

Overview

Definition