Full RREF and rank bounds

Goal and scope

A=[[1,2,3],[2,4,6],[1,1,1]] has row and column rank 2.

A complete integer 3-by-3 matrix, exact elimination and a direct column-span certificate.

Givens and symbols

• calc

• G1 — A has rows (1,2,3),(2,4,6),(1,1,1), with rank over R.

• r_i — nonzero RREF rows
• c_i — original columns

Rules and sources

• calc · prerequisite — Assume the real field, usual coordinate-vector arithmetic, matrix multiplication, and definitions of independence and span; elimination uses invertible elementary row operations.
• mko_definition · cited — This slice handles 2-by-2 or 3-by-3 integer matrices. A nonzero r-minor gives only a lower bound. An upper bound requires all larger minors to vanish or a complete exact RREF. A zero determinant excludes full rank without determining the exact lower rank; equality of row rank and column rank is a theorem. · mko-matrix-rank

Main derivation

A=\begin{pmatrix}1&2&3\\2&4&6\\1&1&1\end{pmatrix}

R_2\leftarrow R_2-2R_1:\quad\begin{pmatrix}1&2&3\\0&0&0\\1&1&1\end{pmatrix}

\begin{pmatrix}1&2&3\\0&0&0\\1&1&1\end{pmatrix}

R_3\leftarrow R_3-R_1:\quad\begin{pmatrix}1&2&3\\0&0&0\\0&-1&-2\end{pmatrix}

\begin{pmatrix}1&2&3\\0&0&0\\0&-1&-2\end{pmatrix}

R_2\leftrightarrow R_3,\quad R_2\leftarrow-R_2:\quad\begin{pmatrix}1&2&3\\0&1&2\\0&0&0\end{pmatrix}

\begin{pmatrix}1&2&3\\0&1&2\\0&0&0\end{pmatrix}

R_1\leftarrow R_1-2R_2:\quad\operatorname{RREF}(A)=\begin{pmatrix}1&0&-1\\0&1&2\\0&0&0\end{pmatrix}

r_1=(1,0,-1),\quad r_2=(0,1,2)

\alpha r_1+\beta r_2=0\Rightarrow\alpha=\beta=0;\quad\operatorname{rowrank}A=2

c_1=(1,2,1),\quad c_2=(2,4,1),\quad c_3=(3,6,1)

c_3=-c_1+2c_2\Rightarrow\operatorname{colrank}A\le2

\begin{pmatrix}1&2\\1&1\end{pmatrix}\text{ in rows 1,3 and columns 1,2}

\det=1-2=-1\ne0\Rightarrow c_1,c_2\text{ independent}

2\le\operatorname{colrank}A\le2,\quad\operatorname{rowrank}A=2

\operatorname{rank}A=2,\quad\det A=0

Substeps and lemmas

No substeps in this guide.

Reverse audits

• S08 · premise_audit · G1, S05, S06, S07 — This example does not prove the general row/column-rank theorem.
• S07 · premise_audit · G1, S06 — The minor certifies independence only; S06 is needed for exact rank.
• S06 · premise_audit · G1 — A nonzero minor gives only a lower bound; this relation supplies the upper bound.
• S05 · premise_audit · G1, S01, S02, S03, S04 — Full spanning and independence give both bounds, not just a count of nonzero rows.
• S04 · premise_audit · G1, S03 — The two nonzero rows have distinct pivots, are independent and span the row space.
• S03 · premise_audit · G1, S02 — No zero division occurs; the inverse of -1 is -1.
• S02 · premise_audit · G1, S01 — Row span is unchanged because old and new rows generate each other.
• S01 · premise_audit · G1 — A zero row does not make the matrix zero or rank zero.

Error controls and negative controls

Invertible operations

Every step is invertible, preserving the exact row span.

Both bounds

A nonzero minor gives a lower bound; a full column-span certificate or complete elimination gives an upper bound.

• det A=0 implies rank A=0. → reject — A nonzero 2-by-2 minor gives rank at least 2.
• A nonzero 2-by-2 minor gives upper bound 2. → reject — I3 has such a minor but rank 3.
• Three nonzero columns imply rank 3. → reject — c3=-c1+2c2 is a nontrivial relation.

Result and limitations

A=[[1,2,3],[2,4,6],[1,1,1]] has row and column rank 2.

Verification and source binding

1 declared checks for this guide; only the listed expressions are covered.

• source commit: b1b2f1dcf8c50d67a93fe52d95f8eef7b3abba9f
• adopted source SHA-256: d8af8464c4da76d69787d86c35189042d83bb8445d6d889fd803182b71cf72bb
• original source SHA-256: 68e30ccbe7cb5fcb0a3a995a4a766df4bcf2e97e70abc01d7195859973bf2fe5
• Lean: NOT_RUN · independent AI: SCOPED_LEAD_AND_BILINGUAL_CONTEXT_REVIEW

Same-source full JSON (formulas, ASTs, controls and revision log)