Inverse of a Matrix
Definition 1. Let $A \in M_{n \times n}(F)$. Then $A$ is invertible if $\exists B \in M_{n \times n}(F)$ such that $AB = BA = I$. The matrix $B$ is called the inverse of $A$, denoted $A^{-1}$.
위와 같이 정의되는 역행렬을 구하는 방법은 여러가지가 있으나, 여기서는 elementary operation을 이용하여 구하는 방법만을 다룬다.
Augmented Matrix
Definition 2. Let $A \in M_{m \times n}(F)$ and $B \in M_{n \times p}(F)$. Then the augmented matrix $(A \vert B)$ is the $m \times (n + p)$ matrix $(A \,\, B)$.
위와 같이 두 개의 행렬을 붙여서 만든 행렬을 augmented matrix, 첨가 행렬이라고 부른다. 역행렬을 구하고자 하는 행렬과 동일한 크기의 단위행렬로 만든 첨가 행렬을 elementary row operation만을 이용해 변환하면 역행렬을 구할 수 있다. 아래의 정리가 그것을 보장해준다.
Lemma
Lemma. Suppose that $A$ and $B$ are matrices having $n$ rows. Then $M(A \vert B) = (MA \vert MB), \forall M \in M_{m \times n}(F)$.
Proof. Note that $(A \vert B)_{ij} = \begin{cases} A_{ij} & \text{if } 1 \leq j \leq n \\ B_{ij} & \text{if } n+1 \leq j \leq p \end{cases}$
For $1 \leq j \leq n, (M(A \vert B))_{ij} = M_{ik}(A \vert B)_{kj} = M_{ik}A_{kj} = (MA)_{ij}.$
For $n+1 \leq j \leq p, (M(A \vert B))_{ij} = M_{ik}(A \vert B)_{kj} = M_{ik}B_{kj} = (MB)_{ij}.$
$\Longrightarrow (M(A \vert B))_{ij} = \begin{cases} (MA)_{ij} & \text{if } 1 \leq j \leq n \\ (MB)_{ij} & \text{if } n+1 \leq j \leq p \end{cases} = (MA \vert MB)_{ij}$. $\blacksquare$
Theorem 1
Theorem 1. Let $A \in M_{n \times n}(F)$. Then
(a) If $A$ is invertible, then $(A \vert I_n)$ can be transformed into $(I_n \vert A^{-1})$ by means of a finite number of elementary row operations,
(b) If $A$ is invertible and $(A \vert I_n)$ is transformed into $(I_n \vert B)$ by means of a finite number of elementary row operations, then $B = A^{-1}$,
(c) If $A$ is not invertible, then any attempt to transform $(A \vert I_n)$ into $(I_n \vert B)$ produces a row whose first $n$ entries are zeros.
Proof.
(a) Note that $A^{-1}$ is invertible so that $A^{-1}$ can be written as $A^{-1} = R_p(I_n) \cdots R_1(I_n)$. Then $R_p \cdots R_1(A \vert I_n) = R_p(I_n) \cdots R_1(I_n)(A \vert I_n)$ = $A^{-1}(A \vert I_n) = (A^{-1}A \vert A^{-1}I_n) = (I_n \vert A^{-1})$. Thus we can obtain $(I_n \vert A^{-1})$ from $(A \vert I_n)$ by means of a finite number of elementary row operations.
(b) Suppose that $R_q \cdots R_1(A \vert I_n) = (I_n \vert B)$. Then $R_q \cdots R_1(A \vert I_n) = R_p(I_n) \cdots R_1(I_n)(A \vert I_n)$. Define $B := R_p(I_n) \cdots R_1(I_n)$. Then $B(A \vert I_n) = (BA \vert BI_n) = (BA \vert B) = (I_n \vert B)$. Thus $BA = I_n$, so $B = A^{-1}$.
(c) Since $A$ is not invertible, rank($A$) < $n$. Then $(A \vert I_n)$ cannot be transformed into $(I_n \vert B)$ because elementary operations are rank-preserving (rank($A$) = rank($I_n$) = $n < n \bigotimes$). $\blacksquare$
