# Linear algebra (Osnabrück 2024-2025)/Part I/Lecture 12/refcontrol

    Invertible matrices

## Definition

Let $K$ be a field,MDLD/field and let $M$ denote an $n\times n$-matrixMDLD/matrix over $K$. Then $M$ is called invertible, if there exists a matrix $A\in \operatorname {Mat} _{n}(K)$ such that
    $A\circ M=E_{n}=M\circ A\,$

## Definition

Let $K$ denote a field.MDLD/field For an invertible matrixMDLD/invertible matrix $M\in \operatorname {Mat} _{n}(K)$, the matrix $A\in \operatorname {Mat} _{n}(K)$ fulfilling
    $A\circ M=E_{n}=M\circ A\,,$
is called the inverse matrix of $M$. It is denoted by
    $M^{-1}.$
The product of invertible matrices is again invertible.

## Definition

For a fieldMDLD/field $K$ and $n\in \mathbb {N} _{+}$, the set of all invertibleMDLD/invertible (matrix) $n\times n$-matricesMDLD/matrices with entrie in $K$ is called the general linear group
$K$
$\operatorname {GL} _{n}\!{\left(K\right)}$

## Definition

Two square matrices $M,N\in \operatorname {Mat} _{n}(K)$ are called similar, if there exists an invertible matrixMDLD/invertible matrix $B$ with
$M=BNB^{-1}$
For a linear mapping $\varphi \colon V\rightarrow V$ the describing matrices with respect to two bases are similar to each other, due to Fact *****.
    Properties of linear mappings

## LemmaCreate referencenumber

Let $K$ be a field, and let $V$ and $W$ be vector spaces over $K$ of dimensions $n$ and $m$. Let
    $\varphi \colon V\longrightarrow W$
be a linear map, described by the matrix $M\in \operatorname {Mat} _{m\times n}(K)$
* $\varphi$ is injectiveMDLD/injective if and only if the columns of the matrix are linearly independent.MDLD/linearly independent
* $\varphi$ is surjectiveMDLD/surjective if and only if the columns of the matrix form a generating systemMDLD/generating system (vs) of $K^{m}$.
* Let $m=n$. Then $\varphi$ is bijectiveMDLD/bijective if and only if the columns of the matrix form a basisMDLD/basis (vs) of $K^{m}$, and this holds if and only if $M$ is invertible.MDLD/invertible (matrix)

### Proof

Let ${\mathfrak {v}}=v_{1},\ldots ,v_{n}$ and ${\mathfrak {w}}=w_{1},\ldots ,w_{m}$ denote the bases of $V$ and $W$ respectively, and let $s_{1},\ldots ,s_{n}$ denote the column vectors of $M$. (1). The mapping $\varphi$ has the property
    $\varphi (v_{j})=\sum _{i=1}^{m}s_{ij}w_{i}\,,$
where $s_{ij}$ is the $i$-th entry of the $j$-th column vector. Therefore,
    $\varphi {\left(\sum _{j=1}^{n}a_{j}v_{j}\right)}=\sum _{j=1}^{n}a_{j}{\left(\sum _{i=1}^{m}s_{ij}w_{i}\right)}=\sum _{i=1}^{m}{\left(\sum _{j=1}^{n}a_{j}s_{ij}\right)}w_{i}\,.$
This is $0$ if and only if $\sum _{j=1}^{n}a_{j}s_{ij}=0$ for all $i$, and this is equivalent with
    $\sum _{j=1}^{n}a_{j}s_{j}=0\,.$
For this vector equation, there exists a nontrivial tuple ${\left(a_{1},\ldots ,a_{n}\right)}$, if and only if the columns are linearly dependent, and this holds if and only if $\varphi$ is not injective. (2). See exercise *****. (3). Let $n=m$. The first equivalence follows from (1) and (2). If $\varphi$ is bijective, then there exists a (linear) inverse mappingMDLD/inverse mapping $\varphi ^{-1}$ with
    $\varphi \circ \varphi ^{-1}=\operatorname {Id} _{W}{\text{ and }}\varphi ^{-1}\circ \varphi =\operatorname {Id} _{V}.$
Let $M$ denote the matrix for $\varphi$, and $N$ the matrix for $\varphi ^{-1}$. The matrix for the identity is the identity matrix.MDLD/identity matrix Because of Lemma 11.10 , we have
    $M\circ N=E_{n}=N\circ M\,$
and therefore $M$ is invertible. The reverse implication is proved similarly.
$\Box$
    Elementary matrices

## Definition

Let $K$ be a fieldMDLD/field and let $M$ be a $m\times n$-matrixMDLD/matrix over $K$. Then the following manipulations on $M$ are called elementary row operations.
* Transpositions of two rows.
* Multiplication of a row with a scalar $s\neq 0$.
* Addition of $a$ times a row to another row.

## Definition

Let $K$ be a field. We denote by $B_{ij}$ the $n\times n$-matrix,MDLD/matrix with entry $1$ at the position $(i,j)$ and entry $0$ everywhere else. Then the following matrices are called elementary matrices.
* $V_{ij}:=E_{n}-B_{ii}-B_{jj}+B_{ij}+B_{ji}$.
* $S_{k}(s):=E_{n}+(s-1)B_{kk}{\text{ for }}s\neq 0$
* $A_{ij}(a):=E_{n}+aB_{ij}{\text{ for }}i\neq j{\text{ and }}a\in K$
In detail, these elementary matrices look as follows.
    $V_{ij}={\begin{pmatrix}1&0&\cdots &\cdots &\cdots &\cdots &0\\\vdots &\ddots &\cdots &\cdots &\cdots &\cdots &\vdots \\0&\cdots &0&\cdots &1&\cdots &0\\\vdots &\cdots &\cdots &1&\cdots &\cdots &\vdots \\0&\cdots &1&\cdots &0&\cdots &0\\\vdots &\cdots &\cdots &\cdots &\cdots &\ddots &\vdots \\0&\cdots &\cdots &\cdots &\cdots &0&1\end{pmatrix}}\,.$
    $S_{k}(s)={\begin{pmatrix}1&0&\cdots &\cdots &\cdots &\cdots &0\\\vdots &\ddots &\ddots &\vdots &\vdots &\vdots &\vdots \\0&\cdots &1&0&\cdots &\cdots &0\\0&\cdots &0&s&0&\cdots &0\\0&\cdots &\cdots &0&1&\cdots &0\\\vdots &\vdots &\vdots &\vdots &\ddots &\ddots &\vdots \\0&\cdots &\cdots &\cdots &\cdots &0&1\end{pmatrix}}\,.$
    $A_{ij}(a)={\begin{pmatrix}1&0&\cdots &\cdots &\cdots &\cdots &0\\\vdots &\ddots &\cdots &\cdots &\cdots &\cdots &\vdots \\0&\cdots &1&\cdots &a&\cdots &0\\\vdots &\cdots &\cdots &\ddots &\cdots &\cdots &\vdots \\0&\cdots &\cdots &\cdots &1&\cdots &0\\\vdots &\cdots &\cdots &\cdots &\cdots &\ddots &\vdots \\0&\cdots &\cdots &\cdots &\cdots &0&1\end{pmatrix}}\,.$
Elementary matrices are invertible, see exercise *****.

## LemmaCreate referencenumber

Let $K$ be a fieldMDLD/field and $M$ a $n\times n$-matrix with entries in $K$. Then the multiplication by elementary matrices from the left with $M$ has the following effects.
* $V_{ij}\circ M=$ exchange of the $i$-th and the $j$-th row of $M$.
* $(S_{k}(s))\circ M=$ multiplication of the $k$-th row of $M$ by $s$.
* $(A_{ij}(a))\circ M=$ addition of $a$-times the $j$-th row of $M$ to the $i$-th row ($i\neq j$).

### Proof

$\Box$
Elementary row operations do not change the solution space of a homogeneous linear system, as shown in Fact *****.

## Theorem
### Proof

$\Box$

## CorollaryCreate referencenumber
### Proof

$\Box$
In particular, for an invertible matrix $M$, there are elementary matrices $E_{1},\ldots ,E_{k}$ such that
    $E_{k}\circ \cdots \circ E_{1}\circ M$
is the identity matrix.
    Finding the inverse matrix

## Method

Let $M$ denote a square matrix.MDLD/square matrix How can we decide whether the matrix is invertible,MDLD/invertible (matrix) and how can we find the inverse matrixMDLD/inverse matrix $M^{-1}$?
For this we write down a table, on the left-hand side we write down the matrix $M$, and on the right-hand side we write down the identity matrix (of the right size). Now we apply on both sides step by step the same elementary row manipulations. The goal is to produce in the left-hand column, starting with the matrix, in the end the identity matrix. This is possible if and only if the matrix is invertible. We claim that we produce, by this method, in the right column the matrix $M^{-1}$ in the end. This rests on the following invariance principle. Every elementary row manipulation can be realized as a matrix multiplication with some elementary matrixMDLD/elementary matrix $E$ from the left. If in the table we have somewhere the pair
    $(M_{1},M_{2}),$
after the next step (in the next line) we have
    $(EM_{1},EM_{2}).$
If we multiply the inverse of the second matrix (which we do not know yet, but we do know its existence, in case the matrix is invertible) with the first matrix, then we get
    $(EM_{1})^{-1}EM_{2}=M_{1}^{-1}E^{-1}EM_{2}=M_{1}^{-1}M_{2}\,.$
This means that this expression is not changed in each single step. In the beginning, this expression equals $M^{-1}E_{n}$, hence in the end, the pair $(E_{n},N)$ must fulfil
    $N=E_{n}^{-1}N=M^{-1}E_{n}=M^{-1}\,.$

## Example Create referencenumber

We want to find for the matrix ${\begin{pmatrix}1&3&1\\4&1&2\\0&1&1\end{pmatrix}}$ its inverse matrixMDLD/inverse matrix $M^{-1}$, following Fact *****.
    Rank of matrices

## Definition

Let $K$ be a field,MDLD/field and let $M$ denote an $m\times n$-matrixMDLD/matrix over $K$. Then the dimensionMDLD/dimension (fgvs) of the linear subspaceMDLD/linear subspace of $K^{m}$, generated by the columns, is called the column rank of the matrix, written
    $\operatorname {rk} \,M.$

## LemmaCreate referencenumber

Let $K$ denote a field,MDLD/field and let $V$ and $W$ denote $K$-vector spacesMDLD/vector spaces of dimensions $n$ and $m$. Let
    $\varphi \colon V\longrightarrow W$
be a linear mappingMDLD/linear mapping which is described by the matrixMDLD/matrix $M\in \operatorname {Mat} _{m\times n}(K)$, with respect to basesMDLD/bases (vs) of the spaces. Then
    $\operatorname {rk} \,\varphi =\operatorname {rk} \,M\,$

### Proof

$\Box$
To formulate the next statement, we introduce row rank of an $m\times n$-matrix to be the dimension of the linear subspace of $K^{n}$ generated by the rows.

## LemmaCreate referencenumber

Let $K$ be a field,MDLD/field and let $M$ denote an $m\times n$-matrixMDLD/matrix over $K$. Then the column rankMDLD/column rank coincides with the row rank.MDLD/row rank The rank equals the number $r$ from

### Proof

In an elementary row manipulation,MDLD/elementary row manipulation the linear subspace generated by the rows is not changed, therefore the row rank is not changed. The row rank of $M$ equals the row rank of the matrix in echelon form obtained in Fact *****. This matrix has row rank $r$, since the first $r$ rows are linearly independent,MDLD/linearly independent and beside this, there are only zero rows. It has also column rank $r$, since the $r$ columns, where there is a new step, are linearly independent, and the other columns are linear combinationsMDLD/linear combinations of these $r$ columns. By exercise *****, the column rank is preserved by elementary row manipulations.
$\Box$
Both ranks coincide, so we only talk about the rank of a matrix.

## CorollaryCreate referencenumber

Let $K$ be a field,MDLD/field and let $M$ denote an $n\times n$-matrixMDLD/matrix
$K$
* $M$ is invertible.
* The rankMDLD/rank (matrix) of $M$ is $n$.
* The rows of $M$ are linearly independent.MDLD/linearly independent
* The columns of $M$ are linearly independent.

### Proof

The equivalence of (2), (3) and (4) follows from the definition and from Fact *****. For the equivalence of (1) and (2), let's consider the linear mappingMDLD/linear mapping
    $\varphi \colon K^{n}\longrightarrow K^{n}$
defined by $M$. The property that the column rank equals $n$, is equivalent with the map being surjective, and this is, due to Corollary 11.9 , equivalent with the map being bijective. Because of Fact *****, bijectivity is equivalent with the matrix being invertible.MDLD/invertible (matrix)
$\Box$