Invertibility

Arun Ram
Department of Mathematics and Statistics
University of Melbourne
Parkville, VIC 3010 Australia
aram@unimelb.edu.au

Last update: 13 August 2013

Invertibility

• An $n\times n$ matrix $A$ is invertible if there is a matrix $A^{-1}$ such that $A{A}^{-1}=A^{-1}A=I_n\text{.}$

${GL}_n\left(R\right)$ is a group with identity $I_n\text{.}$

$B_n,U_n,T_n,S_n$ are all subgroups of ${GL}_n\left(𝔽\right)\text{.}$

• The matrices $e_{ij}$ which contain a 1 in the $i^{\text{th}}$ row and the $j^{\text{th}}$ column and zeros in all other entries are called matrix units.
• The matrices of the form $$\begin{array}{c}I+a{e}_{ij}=\left(\begin{array}{c}1\\ & \ddots & & a\\ \multicolumn{2}{c}{}& \ddots \\ \multicolumn{3}{c}{}& \ddots \\ \multicolumn{4}{c}{}& 1\end{array}\right)\hspace{0.17em}\text{or}\hspace{0.17em}\left(\begin{array}{c}1\\ & \ddots \\ \multicolumn{2}{c}{}& \ddots \\ & a& & \ddots \\ \multicolumn{4}{c}{}& 1\end{array}\right)i\ne j\hspace{0.17em}\text{and}\hspace{0.17em}a\in R,\\ I+e_{ij}+e_{ji}-e_{ii}-e_{jj}=\left(\begin{array}{ccccccccccc}1& \multicolumn{9}{c}{}& 0\\ & \ddots \\ \multicolumn{2}{c}{}& 1\\ \multicolumn{3}{c}{}& 0& \multicolumn{3}{c}{}& 1\\ \multicolumn{4}{c}{}& 1\\ \multicolumn{5}{c}{}& \ddots \\ \multicolumn{6}{c}{}& 1\\ \multicolumn{3}{c}{}& 1& \multicolumn{3}{c}{}& 0\\ \multicolumn{8}{c}{}& 1\\ \multicolumn{9}{c}{}& \ddots \\ 0& \multicolumn{9}{c}{}& 1\end{array}\right),\\ I+(c-1)e_{ii}=\left(\begin{array}{c}1\\ & \ddots \\ \multicolumn{2}{c}{}& 1\\ \multicolumn{3}{c}{}& c\\ \multicolumn{4}{c}{}& 1\\ \multicolumn{5}{c}{}& \ddots \\ \multicolumn{6}{c}{}& 1\end{array}\right)\end{array}$$

are called elementary matrices.

• The row rank of a matrix $A$ is $\text{dim}\hspace{0.17em}\left(\text{span}\left(r_i\right)\right)=r$ where $r_i$ are the vectors determined by the rows of $A\text{.}$

Any matrix $A={GL}_n\left(R\right)$ is a product of elementary matrices.

Any matrix $A\in M_{m\times n}\left(R\right)$ can be written in the form $$A=P\left(\begin{array}{cc}{I}_r& 0\\ 0& 0\end{array}\right)Q$$ where $P\in {GL}_m\left(R\right),$ $Q\in {GL}_n\left(R\right)$ and $r$ is the row rank of $A\text{.}$

Determinants

• The determinant of an $n\times n$ matrix $A=\left(a_{rs}\right)$ $$\text{det}\left(A\right)=\sum _{w\in S_n}\Sigma \left(w\right)a_{1r\left(1\right)}\cdots a_{nr\left(n\right)}\text{.}$$

Laplace expansion $$\text{det}\left(\begin{array}{cccc}{a}_{11}& a_{12}& \cdots & a_{1n}\\ a_{21}& a_{22}& \cdots & a_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ a_{n1}& a_{n2}& \cdots & a_{nn}\end{array}\right)=\sum _i{p}_i\hspace{0.17em}\text{det}\left(\begin{array}{ccc}{a}_{i_1{j}_1}& \cdots & a_{i_1{j}_p}\\ ⋮& \ddots & ⋮\\ a_{i_p{j}_1}& \cdots & a_{i_p{j}_p}\end{array}\right)\left(\begin{array}{ccc}{a}_{i_{p+1}{j}_{p+1}}& \cdots & a_{i_{p+1}{j}_n}\\ ⋮& \ddots & ⋮\\ a_{i_n{j}_{p+1}}& \cdots & a_{i_n{j}_n}\end{array}\right)$$ where $j_1,\dots ,j_n$ is a fixed permutation of $1,2,\dots ,n$ and the sum is over all possible divisions of $1,2,\dots ,n$ into two sets $$i_1<\cdots <i_p\hspace{0.17em}\text{and}\hspace{0.17em}{i}_{p+1}<\cdots <i_n,$$ and $p_i=+1$ or $-1$ according as $i_1,..,i_n$ and $j_1,\dots ,j_n$ are like or unlike derangements of $1,2,\dots ,m\text{.}$

If $A$ and $B$ are $n\times n$ matrices then $$\text{det}\left(AB\right)=\text{det}\left(A\right)\text{det}\left(B\right)\text{.}$$

a)	Let $B$ be the matrix obtained by switching two rows of $A\text{.}$ Then $$\text{det}\left(B\right)=-\text{det}\left(A\right)\text{.}$$
b)	Let $B$ be the matrix obtained by adding a multiple of a row of $A$ to another row of $A\text{.}$ Then $$\text{det}\left(B\right)=\text{det}\left(A\right)\text{.}$$
c)	Let $B$ be the matrix obtained by multiplying a row of $A$ by a constant $c\in R\text{.}$ Then $$\text{det}\left(B\right)=c\text{det}\left(A\right)\text{.}$$

If two rows of $A$ are the same then $\text{det}\left(A\right)=0\text{.}$

• The ${(i,j)}^{\text{th}}$ signed minor or cofactor, $A_{ij},$ of $A$ is $\text{det}\left(\hat{A}\right)$ where $\hat{A}$ is the matrix $A$ with the $i^{\text{th}}$ row and the $j^{\text{th}}$ column removed.

$$\sum _{i=1}^n{a}_{ik}{A}_{hi}=S_{hk}\text{det}\hspace{0.17em}A\text{.}$$

If $\text{det}\left(A\right)$ is a unit in $R$ then $$A^{-1}=\text{det}{\left(a\right)}^{-1}\left(A_{ij}\right)\text{.}$$

Cramer’s rule for $AX=B\text{.}$

Put Thms VII-X of Hodge and Padoe as exercises.

$\lambda \text{-matrices}$

If $A$ is a $p\times q\hspace{0.17em}\lambda \text{-matrix}$ of rank $r$ and $E_1\left(\lambda \right),\dots ,E_r\left(\lambda \right)$ are its invariant factors then there exist $M\in {GL}_p\left(K\left[\lambda \right]\right)$ and $N\in {GL}_q\left(K\left[\lambda \right]\right)$ such that $$MAN=\left(\begin{array}{c}{E}_1\left(\lambda \right)\\ & E_2\left(\lambda \right)& \multicolumn{2}{c}{}& 0\\ \multicolumn{2}{c}{}& \ddots \\ \multicolumn{3}{c}{}& E_r\left(\lambda \right)\\ & 0& \multicolumn{2}{c}{}& 0\\ \multicolumn{5}{c}{}& \ddots \\ \multicolumn{6}{c}{}& 0\end{array}\right)\text{.}$$

Two $p\times q\hspace{0.17em}\lambda \text{-matrices}$ $A$ and $B$ are equivalent if and only if they have the same invariant factors and if and only if they have the same elementary divisors.

Note that these proofs work for any Euclidean domain.

• The characteristic polynomial of $A$ is the polynomial $$\text{det}(A-t{I}_n)\text{.}$$

Cayley-Hamilton Theorem.

Note that the proof of Theorem II §10 Hodge and Padoe!
Theorem III (Hodge and Padoe) gives minimal polynomial.

• A bilinear form on a vector space $V$ over $F$ is a map $⟨,⟩:V\times V\to F$ such that $$\begin{array}{ccc}⟨c_1{v}_1+c_2{v}_2,w⟩& =& c_1⟨v_1,w⟩+c_2⟨v_2,w⟩\text{and}\\ ⟨v,c_1{w}_1+c_2{w}_2⟩& =& c_1⟨v,w_1⟩+c_2⟨v,w_2⟩\end{array}$$ for all $v,v_1,v_2,w,w_1,w_2,\in V$ and $c_1,c_2\in F\text{.}$
• A bilinear form $⟨,⟩:V\times V\to F$ is symmetric if $⟨v,w⟩=⟨w,v⟩$ for all $v,w\in V\text{.}$
• A bilinear form $⟨,⟩:V\times V\to F$ is skew-symmetric if $$⟨v,w⟩=-⟨w,v⟩\hspace{0.17em}\text{for all}\hspace{0.17em}v,w\in V\text{.}$$
• A Hermitian form $⟨,⟩:V\times V\to ℂ$ is a map such that

  a)	$⟨v,w⟩=\overline{⟨w,v⟩}$ for all $v,w\in V\text{.}$
  b)	$⟨c_1{v}_1+c_2{v}_2,w⟩=c_1⟨v_1,w⟩+c_2⟨v_2,w⟩$ $⟨v,c_1{w}_1+c_2{w}_2⟩=\overline{c_1}⟨v,w_1⟩+\overline{c_2}⟨v,w_2⟩\text{.}$ for all $v,v_1,v_2,w,w_1,w_2,\in V$ and $c_1,c_2\in ℂ\text{.}$

• A bilinear form $⟨,⟩:V\times V\to F$ is positive if $$\begin{array}{c}⟨v,v⟩\ge 0\hspace{0.17em}\text{for all}\hspace{0.17em}v\in V\hspace{0.17em}\text{and}\\ ⟨v,v⟩=0\hspace{0.17em}\text{if and only if}\hspace{0.17em}v=0\text{.}\end{array}$$
• A bilinear form $⟨,⟩:V\times V\to F$ is positive semidefinite if $$⟨v,v⟩\ge 0\hspace{0.17em}\text{for all}\hspace{0.17em}v\in V\text{.}$$
• A bilinear form $⟨,⟩:V\times V\to ℝ$ is negative definite if $⟨v,v⟩<0$ for all $v\ne 0,$ $v\in V\text{.}$
• A bilinear form $⟨,⟩:V\times V\to ℝ$ is indefinite if there exists $v,w\in V$ such that $⟨v,v⟩>0$ and $⟨w,w⟩<0\text{.}$

• The adjoint $T^{*}:V\to V$ of a linear transformation $T:V\to V$ is the map determined by $$⟨Tv,w⟩=⟨v,T^{*}w⟩\hspace{0.17em}\text{for all}\hspace{0.17em}w\in V\text{.}$$

• A matrix $A\in M_n\left(F\right)$ is symmetric if $A=A^t\text{.}$
• A matrix $A\in M_n\left(F\right)$ is skew-symmetric if $A=-A^t\text{.}$
• A matrix $A\in M_n\left(ℂ\right)$ is $A={\bar{A}}^t\text{.}$
• A linear transformation $T:V\to V$ is self-adjoint if $T=T^{*}\text{.}$

When is the adjoint well defined?

a)	If $V$ is a vector space over $ℝ$ and $V$ has a symmetric positive definite bilinear form, then $T$ is symmetric if and only if $⟨v,Tw⟩=⟨Tv,w⟩\text{.}$
b)	If $V$ is a vector space over $ℂ$ and $V$ has a Hermitian form, then $T$ is Hermitian if and only if $⟨v,Tw⟩=⟨Tv,w⟩\text{.}$
c)	If $V$ is a vector space over $F$ and $V$ has a skew-symmetric form then $T$ is skew-symmetric if and only if $⟨v,Tw⟩=⟨Tv,w⟩\text{.}$

a)	If $V$ is a vector space over $ℝ$ and $V$ has a symmetric positive definite bilinear form, then $T$ is orthogonal if and only if $⟨v,w⟩=⟨Tv,Tw⟩\text{.}$
b)	If $V$ is a vector space over $ℂ$ and $V$ has a Hermitian form, then $T$ is Unitary if and only if $⟨v,w⟩=⟨Tv,Tw⟩\text{.}$
c)	If $V$ is a vector space over $F$ and and $V$ has a skewed-symmetric form, then $T$ is symplectic if and only if $⟨v,w⟩=⟨Tv,Tw⟩\text{.}$

• A matrix $A\in M_n\left(ℂ\right)$ is normal if $$A{A}^{*}=A^{*}A\text{.}$$

a)	If $A\in M_n\left(ℝ\right)$ is symmetric then there exists $P\in O_n\left(ℝ\right)$ such that $P^{-1}AP$ is diagonal.
b)	If $A\in M_n\left(ℂ\right)$ is Hermitian then there exists $P\in U_n\left(ℂ\right)$ such that $P^{-1}AP$ is diagonal and $P^{-1}AP\in M_n\left(ℝ\right)\text{.}$
c)	$A\in M_n\left(ℂ\right)$ is normal if and only if there exists $P\in U_n\left(ℂ\right)$ such that $P^{-1}AP$ is diagonal.
d)	If $A\in M_n\left(𝔽\right)$ is skew-symmetric then there exists $P\in {Sp}_{2n}\left(F\right)$ such that $P^{-1}AP$ is diagonal.

a)	$V$ is a vector space over $ℝ$ with symmetric positive definite bilinear form and $T:V\to V$ linear transformation. $T$ is orthogonal if and only if $T$ is a change of basis matrix between orthonormal bases.
b)	$V$ is a vector space over $ℂ$ with Hermitian form and $T:V\to V$ linear transformation. $T$ is Hermitian if and only if $T$ is a change of basis matrix between orthonormal bases.
c)	$V$ is a vector space over $F$ with skew-symmetric form and $T:V\to V$ linear transformation. $T$ is symplectic if and only if $T$ is a change of basis between symplectic bases.

aa)	Let $V$ be a vector space over $ℝ$ with positive definite symmetric bilinear form. Then there exists an orthonormal basis.
ab)	Let $A\in M_n\left(ℝ\right)$ be a symmetric positive definite matrix. Then there exists $Q\in {GL}_n\left(ℝ\right)$ such that $QA{Q}^t=I_n\text{.}$
ba)	Let $V$ be a vector space over $ℂ$ with a Hermitian form. Then there exists an orthonormal basis.
bb)	Let $A\in M_n\left(ℂ\right)$ be a Hermitian matrix. Then there exists $Q\in {GL}_n\left(ℂ\right)$ such that $QAQ*=I_n\text{.}$
ca)	Let $V$ be a vector space over $ℝ$ with a symmetric bilinear form. Then there exists an orthogonal basis such that $⟨v_i,v_i⟩=\pm 1$ or $0\text{.}$
cb)	Let $A\in M_n\left(ℝ\right)$ be symmetric. Then there exists $Q\in {GL}_n\left(ℝ\right)$ such that $$QA{Q}^t=\left(\begin{array}{ccc}{I}_p& & 0\\ & -I_q\\ 0& & 0\end{array}\right)$$
da)	Let $V$ be a vector space over $F$ with a skew-symmetric form. Then there exists a symplectic basis.
db)	Let $A$ be a skew-symmetric matrix $A\in M_{2n}\left(𝔽\right)\text{.}$ Then there exists $Q\in {GL}_{2n}\left(𝔽\right)$ such that $$QA{Q}^t=\left(\begin{array}{cc}0& I_n\\ -I_n& 0\end{array}\right)\text{.}$$

Example.

1)	Schwartz Inequality.
2)	Triangle Inequality.
3)	Conics and Quadrics.
4)	Positive definite Exs.

Let $T:V\to V$ be a linear transformation.

• $\text{rank}\left(T\right)=\text{dim}\left(\text{ker}\hspace{0.17em}T\right)$
• $\text{nullity}\left(T\right)=\text{dim}\left(\text{im}\hspace{0.17em}T\right)$

Let $A\in M_{m\times n}\left(F\right)\text{.}$ Then there exists $Q\in {GL}_m\left(F\right)$ and $P\in {GL}_n\left(F\right)$ such that $$QAP=\left(\begin{array}{cc}{I}_r& 0\\ 0& 0\end{array}\right)\text{.}$$

• Martix of a linear transformation T with respect to basis $B=\{b_1,\dots ,b_n\}$ is $A=\left(a_{ij}\right)$ where $$T{b}_j=\sum _{i=1}^n{b}_i{a}_{ij}\text{.}$$

Let $B$ and $B\prime$ be bases and let $T:V\to V$ be a linear transformation. Then let $A$ and $A\prime$ be the matrices of $T$ with respect to $B$ and $B\prime$ respectively. Let $P$ be the change of basis matrix $P⟨b⟩=⟨b\prime ⟩\text{.}$ Then $$A\prime =PA{P}^{-1}\text{.}$$

• An eigenvector of a linear transformation $T:V\to V$ is a vector $v\in V$ such that $Tv=\lambda v$ for some $\lambda \in F\text{.}$
• An eigenvalue of a linear transformation $T:V\to V$ is a vector $\lambda \in F$ such that $Tv=\lambda v$ for some $v\in V\text{.}$

• The characteristic polynomial of a linear transformation $T:V\to V$ is ${\text{ch}}_T\left(T\right)=\text{det}(T-tI)\in F\left[t\right]\text{.}$
• The minimal polynomial of a linear transformation $T:V\to V$ is a polynomial $m_T\left(t\right)\in F\left[t\right]$ such that

  a)	$m_T\left(T\right)=0,$ and
  b)	If $f\left(t\right)\in F\left[T\right]$ and $f\left(t\right)=0$ then $m_T\left(t\right)$ divides $f\left(t\right)$ in $F\left[t\right]\text{.}$

Ex. Matrix in Jordan form, with ${\text{ch}}_T\ne m_T\text{.}$

$m_T\left(t\right)$ exists and is unique.

Let $$m_T\left(t\right)=p_1{\left(t\right)}^{e_1}{p}_2{\left(t\right)}^{e_2}\dots p_k{\left(t\right)}^{e_k}$$ be the prime factorization of the minimal polynomial of $T$ and let $f_i\left(t\right)=\frac{m_T\left(t\right)}{p_i{\left(t\right)}^{e_1}}\text{.}$ Let $E_i=f_i\left(T\right),$ then $$\begin{array}{ccc}{E}_i^2& =& E_i\text{.}\\ E_i{E}_j& =& 0\hspace{0.17em}\text{if}\hspace{0.17em}i\ne j\text{.}\\ 1& =& E_1+E_2+\cdots +E_n\text{.}\end{array}$$

$\lambda$ is an eigenvalue of $T$ if and only if $\lambda$ is a root of the characteristic polynomial of $T,$ ${\text{ch}}_T\left(t\right)\text{.}$

a)	Let $A\in M_n\left(F\right)$ such that ${\text{ch}}_A\left(t\right)$ factors into linear factors in $F\text{.}$ Then there exists $P\in {GL}_n\left(F\right)$ such that $PA{P}^{-1}$ is triangular.
b)	Let $A\in M_n\left(F\right)$ and suppose ${\text{ch}}_F\left(t\right)$ has $n$ distinct roots in $F\text{.}$ Then there exists $P\in {GL}_n\left(F\right)$ such that $PA{P}^{-1}$ is diagonal.

Ex. Does the converse hold?

Proofs for §X.

Let $$m_T\left(t\right)=p_1{\left(t\right)}^{e_1}{p}_2{\left(t\right)}^{e_2}\cdots p_k{\left(t\right)}^{e_k}$$ be the prime factorization of the minimal polynomial of $T$ and let $f_i\left(t\right)=\frac{m_T\left(t\right)}{p_i{\left(t\right)}^{e_1}}\text{.}$ Let $E_i=f_i\left(T\right),$ then $$\begin{array}{ccc}{E}_i^2& =& E_i\text{.}\\ E_i{E}_j& =& 0\hspace{0.17em}\text{if}\hspace{0.17em}i\ne j\text{.}\\ 1& =& E_1+E_2+\dots +E_n\text{.}\end{array}$$

		Proof.
	Let $q_i\left(x\right)\frac{m\left(x\right)}{p_i{\left(x\right)}^{e_i}}\text{.}$ Then the $q_i\left(x\right)$ have $\text{gcd}=1\text{.}$ Since $F\left[x\right]$ is a Euclidean domain there exists $a_i\left(x\right)$ such that $$1=q_1\left(x\right)a_1\left(x\right)+\dots +q_s\left(x\right)a_s\left(x\right)\text{.}$$ Let $f_i\left(x\right)=q_i\left(x\right)a_i\left(x\right)\text{.}$ Then $1=f_1\left(x\right)+\cdots +f_n\left(T\right)\text{.}$ So a) $1=f_1\left(x\right)+\cdots +f_n\left(T\right)\text{.}$ To show: b) $f_i\left(T\right)f_j\left(T\right)=0$ if $i\ne j\text{.}$ Proof. $$\begin{array}{ccc}{f}_i\left(x\right)f_j\left(x\right)& =& q_i\left(x\right)a_i\left(x\right)q_j\left(x\right)a_j\left(x\right)\\ & =& \frac{m\left(x\right)}{p_i{\left(x\right)}^{e_i}}\frac{m\left(x\right)}{p_j{\left(x\right)}^{e_j}}{a}_i\left(x\right)a_j\left(x\right)\text{.}\end{array}$$ So $m\left(x\right)\hspace{0.17em}|\hspace{0.17em}{f}_i\left(x\right)f_j\left(x\right)\text{.}$ So $f_i\left(T\right)f_j\left(T\right)=0\text{.}$ $\square$ To show: c) $f_i{\left(T\right)}^2=f_i\left(T\right)\text{.}$ Proof. $$\begin{array}{ccc}{f}_i\left(T\right)·1& =& f_i\left(T\right)(\sum f_j\left(T\right))\\ & =& f_i{\left(T\right)}^2\text{.}\end{array}$$ $\square$ To show: d) $f_i\left(T\right)V\ne 0\text{.}$ Proof. $$V=\sum _j{f}_i\left(T\right)V\text{.}$$ If $f_i\left(T\right)V=0$ then $$V=\sum _{j\ne i}{f}_j\left(T\right)V\text{.}$$ So $$\begin{array}{ccc}{q}_i\left(T\right)V& =& \sum _{j\ne i}{q}_i\left(T\right)q_j\left(T\right)a_j\left(T\right)V\\ & =& 0\end{array}$$ since $m\left(X\right)\hspace{0.17em}|\hspace{0.17em}{q}_i\left(x\right)q_j\left(x\right)\text{.}$ But $m\left(x\right)$ is the minimal polynomial. So $q_i\left(T\right)V=0\text{.}$ So $f_i\left(T\right)\ne 0\text{.}$ $\square$ To show: e) $f_i\left(T\right)V=\text{nullsp}\left(p_i{\left(T\right)}^{e_i}\right)\text{.}$ Proof. ea) $f_i\left(T\right)V\subseteq \text{nullsp}\left(p_i{\left(T\right)}^{e_i}\right)\text{.}$ Let $v\in f_i\left(T\right)V\text{.}$ Then $$\begin{array}{ccc}{p}_i{\left(T\right)}^{e_i}V& =& p_i{\left(T\right)}^{e_i}{f}_i\left(T\right)v\\ & =& m\left(T\right)a_i\left(T\right)v\\ & =& 0\text{.}\end{array}$$ So $v\in nullsp\left(p_i{\left(T\right)}^{e_i}\right)\text{.}$ eb) Let $v\in \text{nullsp}\left(p_i{\left(T\right)}^{e_i}\right)\text{.}$ Then $v=f_1\left(T\right)v_1+\cdots +f_s\left(T\right)v_s\text{.}$ So $p_i{\left(T\right)}^{e_i}v=0=p_i{\left(T\right)}^{e_i}{f}_1\left(T\right)r_1+\cdots +p_i{\left(T\right)}^{e_i}{f}_s\left(T\right)v_s\text{.}$ $\square$ $\square$

page history