836: For Invertible Square Matrix, from Top Row Downward Through Any Row, Each Row Can Be Changed to Have 1 1 Component and 0 Others Without Duplication to Keep Matrix Invertible

<The previous article in this series | The table of contents of this series | The next article in this series>

description/proof of that for invertible square matrix, from top row downward through any row, each row can be changed to have 1 1 component and 0 others without duplication to keep matrix invertible

---

Topics

About: matrix

---

The table of contents of this article

• Starting Context
• Target Context
• Orientation
• Main Body
• 1: Structured Description
• 2: Note
• 3: Proof

---

Starting Context

• The reader knows a definition of %field name% matrices space.
• The reader admits the proposition that any square matrix is invertible if and only if its determinant is nonzero.
• The reader admits the Laplace expansion of determinant of square matrix.

---

Target Context

• The reader will have a description and a proof of the proposition that for any invertible square matrix, from the top row downward through any row, each row can be changed to have a 1 1 component and 0 others without any duplication to keep the matrix invertible.

---

Orientation

There is a list of definitions discussed so far in this site.

There is a list of propositions discussed so far in this site.

---

Main Body

---

1: Structured Description

Here is the rules of Structured Description.

Entities:
$F$: $\in \{\text{ the fields }\}$
$M$: $\in \{\text{ the }nxnF\text{ invertible matrices }\}$, with the $j$-th row denoted as $M^j$
//

Statements:
$M^1$ can be changed to $(0,...,0,1,0,...,0)$ where $1$ is the $j_1$-th column with the new matrix, $N_1$, invertible.
...
$M^k$ can be changed to $(0,...,0,1,0,...,0)$ where $1$ is the $j_k$-th column with the new matrix, $N_k$, invertible.
$\wedge$
$\{j_1,...,j_k\}$ is distinct.
//

---

2: Note

This proposition directly talks only about "from the top row downward", but of course, some middle rows can be changed, because we can just reorder the rows to move the to-be-changed rows to the top rows, change the top rows, and reorder the rows to restore the original order without changing the invertibleness.

This proposition directly talks only about rows, but of course, columns can be changed, because we can just transpose the matrix, change the rows, and transpose the transposed matrix without changing the invertibleness.

---

3: Proof

Whole Strategy: Step 1: see that any square matrix is invertible if and only if the determinant is nonzero; Step 2: Laplace expand $detM$ with respect to the 1st row, change $M^1$ to $(0,...,0,1,0,...,0)$ where $1$ is the $j_1$-th column with the new matrix, $N_1$, and see that $det{N}_1=1(-1{)}^{s_1}det{m}_1(M)\ne 0$, where $s_1$ is the appropriate natural number and $m_1$ is the operation that takes the appropriate minor; Step 3: Laplace expand $det{m}_1(M)$ with respect to the 1st row, change $M^2$ to $(0,...,0,1,0,...,0)$ where $1$ is the $j_2$-th column with the new matrix, $N_2$, and see that $det{N}_2=1(-1{)}^{s_1}1(-1{)}^{s_2}det{m}_2\circ m_1(M)\ne 0$, where $s_2$ and $m_2$ are likewise; Step 4: suppose that $M^1,...,M^{l-1}$ have been already changed, Laplace expand $det{m}_{l-1}\circ ...,\circ m_1(M)$ with respect to the 1st row, change $M^l$ to $(0,...,0,1,0,...,0)$ where $1$ is the $j_l$-th column with the new matrix, $N_l$, and see that $det{N}_l=1(-1{)}^{s_1}...1(-1{)}^{s_l}det{m}_l\circ ...\circ m_1(M)\ne 0$, where $s_l$ and $m_l$ are likewise.

Step 1:

Any square matrix is invertible if and only if the determinant is nonzero, by the proposition that any square matrix is invertible if and only if its determinant is nonzero.

So, all what we need to check is that $det{N}_k\ne 0$.

Step 2:

Let us Laplace expand $detM$ with respect to the 1st row.

$detM=M_j^1(-1{)}^{1+j}det{m}_{1,j}(M)$, where $m_{1,j}$ is the operator that takes the $1,j$ minor.

As $detM\ne 0$, at least 1 $det{m}_{1,j}(M)$ is nonzero, because otherwise, $detM=M_j^1(-1{)}^{1+j}0=0$, a contradiction.

Let us take such any $j_1$ and change $M^1$ to $(0,...,0,1,0,...,0)$ where $1$ is the $j_1$-th column with the new matrix, $N_1$.

Then, $det{N}_1=1(-1{)}^{1+j_1}det{m}_{1,j_1}(M)\ne 0$: $m_{1,j_1}(N_1)=m_{1,j_1}(M)$.

Let us denote $s_1:=1+j_1$ and $m_1:=m_{1,j_1}$, and $det{N}_1=1(-1{)}^{s_1}det{m}_1(M)\ne 0$.

Step 3:

Let us Laplace expand $det{m}_1(M)$ with respect to the 1st row.

The 1st row consists of $M^2$ without the $j_1$-th column.

There is a $M_{j_2}^2\ne 0$ with the corresponding minor $m_2\circ m_1(M)$ determinant nonzero, because otherwise, each term of the expansion would be zero with the total zero, a contradiction.

$j_2\ne j_1$, because $m_1(M)$ has excluded the $j_1$-th column.

Let us change $M^2$ to $(0,...,0,1,0,...,0)$ where $1$ is the $j_2$-th column with the new matrix, $N_2$.

Then, $det{N}_2=1(-1{)}^{s_1}det{m}_1(N_1)=1(-1{)}^{s_1}1(-1{)}^{s_2}det{m}_2\circ m_1(N_1)=1(-1{)}^{s_1}1(-1{)}^{s_2}det{m}_2\circ m_1(M)\ne 0$: $m_2\circ m_1(N_1)=m_2\circ m_1(M)$, because each of the both sides does not contain any part of $M_1,M_2$.

Step 4:

Let us suppose that $M^1,...,M^{l-1}$ have been already changed with $\{j_1,...,j_{l-1}\}$ distinct and $det{N}_{l-1}=1(-1{)}^{s_1}...1(-1{)}^{s_{l-1}}det{m}_{l-1}\circ ...\circ m_1(M)\ne 0$.

Let us Laplace expand $det{m}_{l-1}\circ ...\circ m_1(M)$ with respect to the 1st row.

The 1st row consists of $M^l$ without the $j_1,...,j_{l-1}$-th columns.

There is a $M_{j_l}^l\ne 0$ with the corresponding minor $m_l\circ m_{l-1}\circ ...\circ m_1(M)$ determinant nonzero, because otherwise, each term of the expansion would be zero with the total zero, a contradiction.

$\{j_1,...,j_l\}$ is distinct, because $m_{l-1}\circ ...\circ m_1(M)$ has excluded the $j_1,...,j_{l-1}$-th columns.

Let us change $M^l$ to $(0,...,0,1,0,...,0)$ where $1$ is the $j_l$-th column with the new matrix, $N_l$.

Then, $det{N}_l=1(-1{)}^{s_1}det{m}_1(N_l)=1(-1{)}^{s_1}1(-1{)}^{s_2}det{m}_2\circ m_1(N_l)=...=1(-1{)}^{s_1}...1(-1{)}^{s_l}det{m}_l\circ ...\circ m_1(N_l)=1(-1{)}^{s_1}...1(-1{)}^{s_l}det{m}_l\circ ...\circ m_1(M)\ne 0$: $m_l\circ ...\circ m_1(N_l)=m_l\circ ...\circ m_1(M)$, because each of the both sides does not contain any part of $M_1,...,M_l$.

Step 5:

So, for each $1\le k\le n$, $det{N}_k\ne 0$.

We can go all down to $k=n$, and $N_n$ will be a reordered identity matrix.

---

References

<The previous article in this series | The table of contents of this series | The next article in this series>