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
- 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 } n x n F \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.
\(\land\)
\(\{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 \(det M\) 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 \text{ } m_1 (M) \neq 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 \text{ } 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 \text{ } m_2 \circ m_1 (M) \neq 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 \text{ } 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 \text{ } m_l \circ ... \circ m_1 (M) \neq 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 \neq 0\).
Step 2:
Let us Laplace expand \(det M\) with respect to the 1st row.
\(det M = M^1_j (-1)^{1 + j} det \text{ } m_{1, j} (M)\), where \(m_{1, j}\) is the operator that takes the \(1, j\) minor.
As \(det M \neq 0\), at least 1 \(det \text{ } m_{1, j} (M)\) is nonzero, because otherwise, \(det M = M^1_j (-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 \text{ } m_{1, j_1} (M) \neq 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 \text{ } m_1 (M) \neq 0\).
Step 3:
Let us Laplace expand \(det \text{ } 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^2_{j_2} \neq 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 \neq 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 \text{ } m_1 (N_1) = 1 (-1)^{s_1} 1 (-1)^{s_2} det \text{ } m_2 \circ m_1 (N_1) = 1 (-1)^{s_1} 1 (-1)^{s_2} det \text{ } m_2 \circ m_1 (M) \neq 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 \text{ } m_{l - 1} \circ ... \circ m_1 (M) \neq 0\).
Let us Laplace expand \(det \text{ } 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^l_{j_l} \neq 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 \text{ } m_1 (N_l) = 1 (-1)^{s_1} 1 (-1)^{s_2} det \text{ } m_2 \circ m_1 (N_l) = ... = 1 (-1)^{s_1} ... 1 (-1)^{s_l} det \text{ } m_l \circ ... \circ m_1 (N_l) = 1 (-1)^{s_1} ... 1 (-1)^{s_l} det \text{ } m_l \circ ... \circ m_1 (M) \neq 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 \neq 0\).
We can go all down to \(k = n\), and \(N_n\) will be a reordered identity matrix.
