avewright/proofwiki-math huggingface dataset:
Theorem: Square Matrix with Duplicate Rows has Zero Determinant

If two rows of a square matrix over a commutative ring $\struct {R, +, \circ}$ are the same, then its determinant is zero.

Proof:
The proof proceeds by induction over $n$, the order of the square matrix.
=== Basis for the Induction ===
Let $n = 2$, which is the smallest natural number for which a square matrix of order $n$ can have two identical rows.
Let $\mathbf A = \sqbrk a_2$ be a square matrix over $R$ with two identical rows.
Then, by definition of determinant:
:$\map \det {\mathbf A} = a_{1 1} a_{2 2} - a_{1 2} a_{2 1} = a_{1 1} a_{2 2} - a_{2 2} a_{1 1} = 0$
{{qed|lemma}}
This is the basis for the induction.
=== Induction Hypothesis ===
Assume for $n \in \N_{\ge 2}$ that any square matrices of order $n$ over $R$ with two identical rows has determinant equal to $0$.
=== Induction Step ===
Let $\mathbf A$ be a square matrix of order $n+1$ over $R$ with two identical rows.
Let $i_1, i_2 \in \set {1, \ldots, n + 1}$ be the indices of the identical rows, and let $i_1 < i_2$.
Let $i \in \set {1, \ldots, n + 1}$.
Let $\map {\mathbf A} {i; 1}$ denote the submatrix obtained from $\mathbf A$ by removing row $i$ and column $1$.
If $i \ne i_1$ and $i \ne i_2$, then $\map {\mathbf A} {i; 1}$ still contains two identical rows.
By the induction hypothesis:
:$\map \det {\map {\mathbf A} {i; 1} } = 0$
Now consider the matrices $\map {\mathbf A} {i_1; 1}$ and $\map {\mathbf A} {i_2; 1}$.
Let $r_j$ denote row $j$ of $\map {\mathbf A} {i_1; 1}$.
If we perform the following sequence of $i_2 - i_1 - 1$ elementary row operations on $\map {\mathbf A} {i_1; 1}$:
:$r_{i_1} \leftrightarrow r_{i_1 + 1} \ ; \ r_{i_1 + 1} \leftrightarrow r_{i_1 + 2}  \ ;  \ \ldots  \  ;  \ r_{i_2 - 1} \leftrightarrow r_{i_2}$
we will transform $\map {\mathbf A} {i_1; 1}$ into $\map {\mathbf A} {i_2; 1}$.
From Determinant with Rows Transposed:
:$\map \det {\map {\mathbf A} {i_1; 1} } = \paren {-1}^{i_2 - i_1 - 1} \map \det {\map {\mathbf A} {i_2; 1} }$
Then:
{{begin-eqn}}
{{eqn | l = \map \det {\mathbf A}
      | r = \sum_{k \mathop = 1 }^{n + 1} a_{k 1} \paren {-1}^{k + 1} \map \det {\map {\mathbf A} {k; 1} }
      | c = expanding the determinant along column $1$
}}
{{eqn | r = a_{i_1 1} \paren {-1}^{i_1 + 1} \map \det {\map {\mathbf A} {i_1; 1} } + a_{i_2 1} \paren {-1}^{i_2 + 1} \map \det {\map {\mathbf A} {i_2; 1} }
}}
{{eqn | r = a_{i_2 1} \paren {-1}^{i_1 + 1 + i_2 - i_1 - 1} \map \det {\map {\mathbf A} {i_2; 1} } + a_{i_2 1} \paren {-1}^{i_2 + 1} \map \det {\map {\mathbf A} {i_2; 1} }
}}
{{eqn | r = 0
}}
{{end-eqn}}
{{qed}}
Theorem: Square Matrix with Duplicate Rows has Zero Determinant

If two rows of a square matrix over a commutative ring $\struct {R, +, \circ}$ are the same, then its determinant is zero.

Proof:
Suppose that $\forall x \in R: x + x = 0 \implies x = 0$.
From Determinant with Rows Transposed, if you exchange two rows of a square matrix, the sign of its determinant changes.
If you exchange two identical rows of a square matrix, then the sign of its determinant changes from $D$, say, to $-D$.
But the matrix stays the same.
So $D = -D$ and so $D = 0$.
{{qed}}
Theorem: Determinant with Row Multiplied by Constant

Let $\mathbf A = \sqbrk a_n$ be a square matrix of order $n$.
Let $\map \det {\mathbf A}$ be the determinant of $\mathbf A$.
Let $\mathbf B$ be the matrix resulting from one row of $\mathbf A$ having been multiplied by a constant $c$.
Then:
:$\map \det {\mathbf B} = c \map \det {\mathbf A}$
That is, multiplying one row of a square matrix by a constant multiplies its determinant by that constant.

Proof:
Let $\mathbf A = \sqbrk a_n$ be a square matrix of order $n$.
Let $e$ be the elementary row operation that multiplies rows $i$ by the scalar$c$.
Let $\mathbf B = \map e {\mathbf A}$.
Let $\mathbf E$ be the elementary row matrix corresponding to $e$.
From Elementary Row Operations as Matrix Multiplications:
:$\mathbf B = \mathbf E \mathbf A$
From Determinant of Elementary Row Matrix: Exchange Rows:
:$\map \det {\mathbf E} = c$
Then:
{{begin-eqn}}
{{eqn | l = \map \det {\mathbf B}
      | r = \map \det {\mathbf E \mathbf A}
      | c = Determinant of Matrix Product
}}
{{eqn | r = c \map \det {\mathbf A}
      | c = as $\map \det {\mathbf E} = c$
}}
{{end-eqn}}
Hence the result.
{{qed}}
Theorem: Determinant with Row Multiplied by Constant

Let $\mathbf A = \sqbrk a_n$ be a square matrix of order $n$.
Let $\map \det {\mathbf A}$ be the determinant of $\mathbf A$.
Let $\mathbf B$ be the matrix resulting from one row of $\mathbf A$ having been multiplied by a constant $c$.
Then:
:$\map \det {\mathbf B} = c \map \det {\mathbf A}$
That is, multiplying one row of a square matrix by a constant multiplies its determinant by that constant.

Proof:
Let:
:<nowiki>$\mathbf A = \begin {bmatrix}
a_{1 1} & a_{1 2} & \cdots & a_{1 n} \\
a_{2 1} & a_{2 2} & \cdots & a_{2 n} \\
 \vdots &  \vdots & \ddots &  \vdots \\
a_{r 1} & a_{r 2} & \cdots & a_{r n} \\
 \vdots &  \vdots & \ddots &  \vdots \\
a_{n 1} & a_{n 2} & \cdots & a_{n n} \\
\end {bmatrix}$</nowiki>
:<nowiki>$\mathbf B = \begin{bmatrix}
b_{1 1} & b_{1 2} & \ldots & b_{1 n} \\
b_{2 1} & b_{2 2} & \ldots & b_{2 n} \\
 \vdots &  \vdots & \ddots &  \vdots \\
b_{r 1} & b_{r 2} & \cdots & b_{r n} \\
 \vdots &  \vdots & \ddots &  \vdots \\
b_{n 1} & b_{n 2} & \cdots & b_{n n} \\
\end{bmatrix} = \begin{bmatrix}
a_{1 1} & a_{1 2} & \ldots & a_{1 n} \\
a_{2 1} & a_{2 2} & \ldots & a_{2 n} \\
 \vdots &  \vdots & \ddots &  \vdots \\
c a_{r 1} & c a_{r 2} & \cdots & c a_{r n} \\
 \vdots &  \vdots & \ddots &  \vdots \\
a_{n 1} & a_{n 2} & \cdots & a_{n n} \\
\end{bmatrix}$</nowiki>
Then from the definition of the determinant:
{{begin-eqn}}
{{eqn | l = \map \det {\mathbf B}
      | r = \sum_\lambda \paren {\map \sgn \lambda \prod_{k \mathop = 1}^n b_{k \map \lambda k} }
      | c = 
}}
{{eqn | r = \sum_\lambda \map \sgn \lambda a_{1 \map \lambda 1} a_{2 \map \lambda 2} \cdots c a_{r \map \lambda r} \cdots a_{n \map \lambda n}
      | c = 
}}
{{end-eqn}}
The constant $c$ is a factor of all the terms in the $\sum_\lambda$ expression and can be taken outside the summation:
{{begin-eqn}}
{{eqn | l = \map \det {\mathbf B}
      | r = c \sum_\lambda \map \sgn \lambda a_{1 \map \lambda 1} a_{2 \map \lambda 2} \cdots a_{r \map \lambda r} \cdots a_{n \map \lambda n}
      | c = 
}}
{{eqn | r = c \sum_\lambda \paren {\map \sgn \lambda \prod_{k \mathop = 1}^n a_{k \map \lambda k} }
      | c = 
}}
{{eqn | r = c \, \map \det {\mathbf A}
      | c = 
}}
{{end-eqn}}
{{qed}}
Theorem: Multiple of Row Added to Row of Determinant

Let <nowiki>$\mathbf A = \begin {bmatrix}
a_{1 1} & a_{1 2} & \cdots & a_{1 n} \\
 \vdots &  \vdots & \ddots &  \vdots \\
a_{r 1} & a_{r 2} & \cdots & a_{r n} \\
 \vdots &  \vdots & \ddots &  \vdots \\
a_{s 1} & a_{s 2} & \cdots & a_{s n} \\
 \vdots &  \vdots & \ddots &  \vdots \\
a_{n 1} & a_{n 2} & \cdots & a_{n n} \\
\end {bmatrix}$</nowiki> be a square matrix of order $n$.
Let $\map \det {\mathbf A}$ denote the determinant of $\mathbf A$.
Let <nowiki>$\mathbf B = \begin{bmatrix}
a_{1 1}             & a_{1 2}             & \cdots &             a_{1 n} \\
 \vdots             & \vdots              & \ddots &              \vdots \\
a_{r 1} + k a_{s 1} & a_{r 2} + k a_{s 2} & \cdots & a_{r n} + k a_{s n} \\
 \vdots             & \vdots              & \ddots &              \vdots \\
a_{s 1}             & a_{s 2}             & \cdots &             a_{s n} \\
 \vdots             & \vdots              & \ddots &              \vdots \\
a_{n 1}             & a_{n 2}             & \cdots &             a_{n n} \\
\end{bmatrix}$</nowiki>.
Then:
:$\map \det {\mathbf B} = \map \det {\mathbf A}$.
That is, the value of a determinant remains unchanged if a constant multiple of any row is added to any other row.

Proof:
Let $e$ be the elementary row operation that adds $k$ times row $r$ to row $s$.
Let $\mathbf B = \map e {\mathbf A}$.
Let $\mathbf E$ be the elementary row matrix corresponding to $e$.
From Elementary Row Operations as Matrix Multiplications:
:$\mathbf B = \mathbf E \mathbf A$
From Determinant of Elementary Row Matrix: Scale Row and Add:
:$\map \det {\mathbf E} = 1$
Then:
{{begin-eqn}}
{{eqn | l = \map \det {\mathbf B}
      | r = \map \det {\mathbf E \mathbf A}
      | c = Determinant of Matrix Product
}}
{{eqn | r = \map \det {\mathbf A}
      | c = as $\map \det {\mathbf E} = 1$
}}
{{end-eqn}}
Hence the result.
{{qed}}
Theorem: Determinant of Matrix Product

Let $\mathbf A = \sqbrk a_n$ and $\mathbf B = \sqbrk b_n$ be a square matrices of order $n$.
Let $\map \det {\mathbf A}$ be the determinant of $\mathbf A$.
Let $\mathbf A \mathbf B$ be the (conventional) matrix product of $\mathbf A$ and $\mathbf B$.
Then:
:$\map \det {\mathbf A \mathbf B} = \map \det {\mathbf A} \map \det {\mathbf B}$
That is, the determinant of the product is equal to the product of the determinants.

Proof:
Consider two cases:
:$(1): \quad \mathbf A$ is singular.
:$(2): \quad \mathbf A$ is nonsingular.
=== Proof of case $1$ ===
Assume $\mathbf A$ is singular. 
Then:
:$\map \det {\mathbf A} = 0$
Also if $\mathbf A$ is singular then so is $\mathbf A \mathbf B$.
Indeed, if $\mathbf A \mathbf B$ has an inverse $\mathbf C$, then:
:$\mathbf A \mathbf B \mathbf C = \mathbf I$
whereby $\mathbf B \mathbf C$ is a right inverse of $\mathbf A$.
It follows by Left or Right Inverse of Matrix is Inverse that in that case $\mathbf B \mathbf C$ is the inverse of $A$.
It follows that:
:$\map \det {\mathbf A \mathbf B} = 0$
Thus:
:$0 = 0 \times \map \det {\mathbf B}$
that is:
:$\map \det {\mathbf A \mathbf B} = \map \det {\mathbf A} \map \det {\mathbf B}$
{{qed|lemma}}
=== Proof of case $2$ ===
Assume $\mathbf A$ is nonsingular.
Then $\mathbf A$ is a product of elementary row matrices, $\mathbf E$.
Let $\mathbf A = \mathbf E_k \mathbf E_{k - 1} \cdots \mathbf E_1$.
So:
:$\map \det {\mathbf A \mathbf B} = \map \det {\mathbf E_k \mathbf E_{k - 1} \cdots \mathbf E_1 \mathbf B}$
It remains to be shown that for any square matrix $\mathbf D$ of order $n$:
:$\map \det {\mathbf E \mathbf D} = \map \det {\mathbf E} \map \det {\mathbf D}$
Let $e_i \paren {\mathbf I} = \mathbf E_i$ for all $i \in \closedint 1 k$.
Then:
{{begin-eqn}}
{{eqn | l = \map \det {\mathbf E \mathbf D}
      | r = \map \det {\mathbf E_k \mathbf E_{k - 1} \dotsm \mathbf {E_1} \mathbf D}
      | c = Elementary Row Operations as Matrix Multiplications
}}
{{eqn | r = \map \det {e_k e_{k - 1} \cdots e_1 \paren {\mathbf D} }
      | c = Effect of Sequence of Elementary Row Operations on Determinant
}}
{{eqn | r = \alpha \map \det {\mathbf D}
      | c = 
}}
{{end-eqn}}
and:
{{begin-eqn}}
{{eqn | l = \map \det {\mathbf E}
      | r = \map \det {\mathbf E_k \mathbf E_{k - 1} \cdots \mathbf {E_1} \mathbf I}
      | c = Elementary Row Operations as Matrix Multiplications
}}
{{eqn | r = \map \det {e_k e_{k - 1} \cdots e_1 \paren {\mathbf I} }
      | c = Effect of Sequence of Elementary Row Operations on Determinant
}}
{{eqn | r = \alpha \map \det {\mathbf I}
      | c = Unit Matrix is Unity of Ring of Square Matrices
}}
{{end-eqn}}
From Determinant of Unit Matrix:
:$\map \det {\mathbf E} = \alpha$
Hence:
:$\map \det {\mathbf E \mathbf D} = \map \det {\mathbf E} \map \det {\mathbf D}$
{{qed|lemma}}
Therefore:
:$\map \det {\mathbf A \mathbf B} = \map \det {\mathbf A} \map \det {\mathbf B}$
as required.
{{qed}}
Theorem: Determinant of Matrix Product

Let $\mathbf A = \sqbrk a_n$ and $\mathbf B = \sqbrk b_n$ be a square matrices of order $n$.
Let $\map \det {\mathbf A}$ be the determinant of $\mathbf A$.
Let $\mathbf A \mathbf B$ be the (conventional) matrix product of $\mathbf A$ and $\mathbf B$.
Then:
:$\map \det {\mathbf A \mathbf B} = \map \det {\mathbf A} \map \det {\mathbf B}$
That is, the determinant of the product is equal to the product of the determinants.

Proof:
The Cauchy-Binet Formula gives:
:$\ds \map \det {\mathbf A \mathbf B} = \sum_{1 \mathop \le j_1 \mathop < j_2 \mathop < \cdots \mathop < j_m \le n} \map \det {\mathbf A_{j_1 j_2 \ldots j_m} } \map \det {\mathbf B_{j_1 j_2 \ldots j_m} }$
where:
:$\mathbf A$ is an $m \times n$ matrix
:$\mathbf B$ is an $n \times m$ matrix.
:For $1 \le j_1, j_2, \ldots, j_m \le n$:
::$\mathbf A_{j_1 j_2 \ldots j_m}$ denotes the $m \times m$ matrix consisting of columns $j_1, j_2, \ldots, j_m$ of $\mathbf A$.
::$\mathbf B_{j_1 j_2 \ldots j_m}$ denotes the $m \times m$ matrix consisting of rows $j_1, j_2, \ldots, j_m$ of $\mathbf B$.
When $m = n$, the only set $j_1, j_2, \ldots, j_m$ that fulfils $1 \le j_1 < j_2 < \cdots < j_m \le n$ is $\set {1, 2, \ldots, n}$.
Hence the result.
{{qed}}
Theorem: Determinant with Unit Element in Otherwise Zero Row

Let $D$ be the determinant:
:<nowiki>$D = \begin {vmatrix}
      1 &       0 & \cdots &       0 \\
b_{2 1} & b_{2 2} & \cdots & b_{2 n} \\
 \vdots &  \vdots & \ddots &  \vdots \\
b_{n 1} & b_{n 2} & \cdots & b_{n n}
\end {vmatrix}$</nowiki>
Then:
:<nowiki>$D = \begin {vmatrix}
b_{2 2} & \cdots & b_{2 n} \\
 \vdots & \ddots &  \vdots \\
b_{n 2} & \cdots & b_{n n}
\end {vmatrix}$</nowiki>

Proof:
We refer to the elements of:
:<nowiki>$\begin {vmatrix}
      1 &       0 & \cdots &       0 \\
b_{2 1} & b_{2 2} & \cdots & b_{2 n} \\
 \vdots &  \vdots & \ddots &  \vdots \\
b_{n 1} & b_{n 2} & \cdots & b_{n n}
\end {vmatrix}$</nowiki>
as $\begin {vmatrix} b_{i j} \end {vmatrix}$.
Thus $b_{1 1} = 1, b_{1 2} = 0, \ldots, b_{1 n} = 0$.
Then from the definition of determinant:
{{begin-eqn}}
{{eqn | l = D
      | r = \sum_\lambda \paren {\map \sgn \lambda \prod_{k \mathop = 1}^n b_{k \map \lambda k} }
      | c = 
}}
{{eqn | r = \sum_{\lambda} \map \sgn \lambda b_{1 \map \lambda 1} b_{2 \map \lambda 2} \cdots b_{n \map \lambda n}
      | c = 
}}
{{end-eqn}}
Now we note:
{{begin-eqn}}
{{eqn | l = \map \lambda 1 = 1
      | o = \implies
      | r = b_{1 \map \lambda 1} b_{2 \map \lambda 2} \cdots b_{n \map \lambda n} = 1
      | c = 
}}
{{eqn | l = \map \lambda 1 \ne 1
      | o = \implies
      | r = b_{1 \map \lambda 1} b_{2 \map \lambda 2} \cdots b_{n \map \lambda n} = 0
      | c = 
}}
{{end-eqn}}
So only those permutations on $\N^*_n$ such that $\map \lambda 1 = 1$ contribute towards the final summation.
Thus we have:
:$\ds D = \sum_\mu \map \sgn \mu b_{2 \map \mu 2} \cdots b_{n \map \mu n}$
where $\mu$ is the collection of all permutations on $\N^*_n$ which fix $1$.
Hence the result.
{{Qed}}
Theorem: Equality of Polynomials

$f$ and $g$ are equal as polynomials {{iff}} $f$ and $g$ are equal as functions.
Thus we can say $f = g$ without ambiguity as to what it means.
{{explain|In the exposition, the term was "equal as forms", but it has now morphed into "equal as polynomials". Needs to be resolved.}}

Proof:
{{ProofWanted|Proof missing. Also, I am not sure how general this result can be made. My suspicion is that if a comm. ring with $1$, $R$ has no idempotents save $0$ and $1$, then the result continue to hold, but not sure at the moment.}}
Category:Polynomial Theory
gez7nlokbtddy1lrqogfytpdsav6gri
Theorem: Value of Adjugate of Determinant

Let $D$ be the determinant of order $n$.
Let $D^*$ be the adjugate of $D$.
Then $D^* = D^{n - 1}$.

Proof:
Let <nowiki>$\mathbf A = \begin {bmatrix}  a_{11} & a_{12} & \cdots & a_{1n} \\
a_{21} & a_{22} & \cdots & a_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
a_{n1} & a_{n2} & \cdots & a_{nn} \end {bmatrix}$</nowiki> and <nowiki>$\mathbf A^* = \begin {bmatrix} A_{11} & A_{12} & \cdots & A_{1n} \\
A_{21} & A_{22} & \cdots & A_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
A_{n1} & A_{n2} & \cdots & A_{nn} \end {bmatrix}$</nowiki>.
Thus:
:<nowiki>$\paren {\mathbf A^*}^\intercal = \begin {bmatrix} A_{11} & A_{21} & \cdots & A_{n1} \\
A_{12} & A_{22} & \cdots & A_{n2} \\
\vdots & \vdots & \ddots & \vdots \\
A_{1n} & A_{2n} & \cdots & A_{nn} \end {bmatrix}$</nowiki>
is the transpose of $\mathbf A^*$.
Let $c_{ij}$ be the typical element of $\mathbf A \paren {\mathbf A^*}^\intercal$.
Then by definition of matrix product:
:$\ds c_{ij} = \sum_{k \mathop = 1}^n a_{ik} A_{jk}$
Thus by the {{Corollary|Laplace Expansion Theorem for Determinants}}:
:$c_{ij} = \delta_{ij} D$
So by Determinant of Diagonal Matrix:
:<nowiki>$\map \det {\mathbf A \paren {\mathbf A^*}^\intercal} = \begin {vmatrix} D & 0 & \cdots & 0 \\
 0 & D & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
 0 & 0 & \cdots & D \end {vmatrix} = D^n$</nowiki>
From Determinant of Matrix Product:
:$\map \det {\mathbf A} \map \det {\paren {\mathbf A^*}^\intercal} = \map \det {\mathbf A \paren {\mathbf A^*}^\intercal}$
From Determinant of Transpose:
:$\map \det {\paren {\mathbf A^*}^\intercal} = \map \det {\mathbf A^*}$
Thus as $D = \map \det {\mathbf A}$ and $D^* = \map \det {\mathbf A^*}$ it follows that:
:$DD^* = D^n$
Now if $D \ne 0$, the result follows.
However, if $D = 0$ we need to show that $D^* = 0$.
Let <nowiki>$D^* = \begin {vmatrix} A_{11} & A_{12} & \cdots & A_{1n} \\
A_{21} & A_{22} & \cdots & A_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
A_{n1} & A_{n2} & \cdots & A_{nn} \end {vmatrix}$</nowiki>.
Suppose that at least one element of $\mathbf A$, say $a_{rs}$, is non-zero (otherwise the result follows immediately).
By Laplace Expansion Theorem for Determinants and {{Corollary|Laplace Expansion Theorem for Determinants}}, we can expand $D$ by row $r$, and get:
:$\ds D = 0 = \sum_{j \mathop = 1}^n A_{ij} t_j, \forall i = 1, 2, \ldots, n$
for all $t_1 = a_{r1}, t_2 = a_{r2}, \ldots, t_n = a_{rn}$.
But $t_s = a_{rs} \ne 0$.
So, by '''(work in progress)''':
:<nowiki>$D^* = \begin {vmatrix} A_{11} & A_{12} & \cdots & A_{1n} \\
A_{21} & A_{22} & \cdots & A_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
A_{n1} & A_{n2} & \cdots & A_{nn} \end {vmatrix} = 0$</nowiki>
{{WIP|One result to document, I've got to work out how best to formulate it.}}
Category:Determinants
myyacix9v4p1mb2ewe0f4pj818ognyg
Theorem: Determinant of Diagonal Matrix

Let $\mathbf A = \begin{bmatrix}
a_{11} & 0 & \cdots & 0 \\
0 & a_{22} & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & a_{nn} \\
\end{bmatrix}$ be a diagonal matrix.
Then the determinant of $\mathbf A$ is the product of the elements of $\mathbf A$.
That is:
:$\ds \map \det {\mathbf A} = \prod_{i \mathop = 1}^n a_{ii}$

Proof:
As a diagonal matrix is also a triangular matrix (both upper and lower), the result follows directly from Determinant of Triangular Matrix.
{{qed}}
Category:Determinants
Category:Diagonal Matrices
46j7gt7zea6di1bocalbw6n08ipn7hx
Theorem: Row Equivalence is Equivalence Relation

Row equivalence is an equivalence relation.

Proof:
In the following, $\mathbf A$, $\mathbf B$ and $\mathbf C$ denote arbitrary matrices in a given matrix space $\map \MM {m, n}$ for $m, n \in \Z_{>0}$.
We check in turn each of the conditions for equivalence:
Theorem: Matrix is Row Equivalent to Reduced Echelon Matrix

Let $\mathbf A = \sqbrk a_{m n}$ be a matrix of order $m \times n$ over a field $F$.
Then $A$ is row equivalent to a reduced echelon matrix of order $m \times n$.

Proof:
{{Recall|Gaussian Elimination}}
{{:Definition:Gaussian Elimination/Procedure}}
Hence the result.
{{qed}}
Theorem: Square Matrix is Row Equivalent to Triangular Matrix

Let $\mathbf A = \sqbrk a_n$ be a square matrix of order $n$ over a commutative ring $R$.
Then $\mathbf A$ can be converted to an upper or lower triangular matrix by elementary row operations.

Proof:
Let $\mathbf A$ be a square matrix of order $n$.
We proceed by induction on $n$, the number of rows of $\mathbf A$.
=== Basis for the Induction ===
For $n = 1$, we have a matrix of just one element, which is trivially diagonal, hence both upper and lower triangular.
This is the basis for the induction.
=== Induction Hypothesis ===
Fix $n \in \N$, and assume all $n \times n$-matrices can be upper triangularised by elementary row operations. 
If $R$ is a field, assume all $n \times n$-matrices can be upper triangularised by elementary row operations of type $2$.
This forms our induction hypothesis.
=== Induction Step ===
Let $\mathbf A = \sqbrk a_{n + 1}$ be a square matrix of order $n + 1$.
When the first column of $\mathbf A$ contains only zeroes, it is upper triangularisable {{iff}} the submatrix $\map {\mathbf A} {1; 1}$ is.
Each elementary row operation used in triangularisation process of the submatrix $\map {\mathbf A} {1; 1}$ will not change the zeros of the first column of $\mathbf A$.
So when $\map {\mathbf A} {1; 1}$ is upper triangularised, then $A$ will also be upper triangularised.
From the induction hypothesis, we conclude that $\mathbf A$ can be upper triangularised by elementary row operations.
Now suppose that its first column contains a non-zero value.
Suppose that $a_{1 1} = 0$.
Let $j$ be the smallest row index such that $a_{j 1} \ne 0$, and note that $j$ exists by assumption.
Now apply the following operation of type $2$:
:$r_1 \to r_1 + r_j$
As $a_{j 1} \ne 0$, this enforces $a_{1 1} \ne 0$, and we continue as in the case below.
Suppose $a_{1 1} \ne 0$. 
We use the following operations for all $j \in \set {2, \ldots, n + 1}$:
:$(1): \quad$ Put $c = a_{j 1}$.
:$(2): \quad r_j \to a_{1 1} r_j$
:$(3): \quad r_j \to r_j - c r_1$
This will put the first column to zero (except for the first element, $a_{1 1}$).
It follows that $\mathbf A$ can be upper triangularised {{iff}} the submatrix $\map {\mathbf A} {1; 1}$ can.
Again, the induction hypothesis renders $\mathbf A$ upper triangularisable by elementary row operations.
This completes the case distinction, and hence the result follows by induction.
To put the matrix $\mathbf A$ into lower triangular form, just do the same thing, but start with the last column and the last diagonal element $a_{n + 1 \; n + 1}$.
{{qed}}