MATH 417 Lecture 21

« previous | Tuesday, April 8, 2014 | next »

Special Matrices

• (strictly) Diagonally Dominant: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_{ii} > \sum_{i\nej} (a_{ij})}
• (strictly) Positive Definite: $A=A^{T}$

Both types are nonsingular, and

Theorem. If $A$ is diagonally dominant, then we can perform gaussian elimination without pivoting: $A=L\,U$; $L={\begin{bmatrix}1&0\\\ell _{ij}&1\end{bmatrix}}$; $U={\begin{bmatrix}u_{11}&u_{ij}\\0&u_{nn}\end{bmatrix}}$

Proof. After one step of gaussian elimination, we go from matrix $A^{(1)}$ to $A^{(2)}$, where $a_{i1}^{(2)}=0$ for $i\neq 1$ by adding (row 1) × $-{\frac {a_{i1}^{(1)}}{a_{11}^{(1)}}}$ to the $i$-th row:

$a_{ij}^{(2)}=a_{ij}^{(1)}-{\frac {a_{i1}^{(1)}}{a_{11}^{(1)}}}\,a_{1j}^{(1)}$

This is possible because $a_{11}\neq 0$ by the diagonally dominant property:

${\begin{aligned}\sum _{j\neq i}\left|a_{ij}^{(2)}\right|&=\sum _{j\neq i}\left|a_{ij}^{(1)}-{\frac {a_{i1}^{(1)}}{a_{11}^{(1)}}}\,a_{1j}^{(1)}\right|\\&\leq \sum _{j\neq i}\left|a_{ij}^{(1)}\right|+\sum _{j\neq i}\left|{\frac {a_{i1}^{(1)}}{a_{11}^{(1)}}}\right|\cdot \left|a_{1j}^{(1)}\right|\\&\leq \underbrace {\left|a_{ii}^{(1)}\right|-\left|a_{i1}^{(1)}\right|} _{{\mbox{row}}\ i}+\left|{\frac {a_{i1}^{(1)}}{a_{11}^{(1)}}}\right|\,\left(\underbrace {\sum _{j=2}^{n}\left|a_{1j}^{(1)}\right|} _{<\left|a_{11}^{(1)}\right|-\left|a_{1i}^{(1)}\right|}\right)\\&<\left|a_{ii}^{(1)}\right|-\left|{\frac {a_{i1}^{(1)}}{a_{11}^{(1)}}}\,a_{1i}^{(1)}\right|\\&\leq a_{ii}^{(2)}\end{aligned}}$

The theorem holds by induction.

quod erat demonstrandum

Theorem. If $A$ is positive definite, then

$a_{ii}>0$ for $i=1,2,\ldots ,n$
$a_{ij}^{2}<a_{ii}\,a_{ij}$ for $i\neq j$
$\max _{1\leq i,j\leq n}\left|a_{ij}\right|=\max _{1\leq i\leq n}\left|a_{ii}\right|$

Proof. Let $A$ be a $n\times n$ matrix with entries $\left(a_{ij}\right)$

By definition, we have $A=A^{T}$ (or $A={\overline {A^{T}}}$, if $a\in \mathbb {C} _{n}$)

Define the minor of matrix $A$ to be:

$M_{ii}={\begin{bmatrix}a_{11}&\dots &a_{1i}\\\vdots &\ddots &\vdots \\a_{i1}&\dots &a_{ii}\end{bmatrix}}$ for $i=1,2,\ldots ,n$

Lemma: $A$ is positive definite if and only if $\left|M_{ii}\right|>0$.

Let's start with $n=1$:

$A=\left(a_{11}\right)$, ${\vec {x}}=(x_{1})\neq 0$. ${\vec {x}}^{T}\,A\,{\vec {x}}=a_{11}\,x^{2}>0$ if and only if $a_{11}>0$

For $n=2$:

$A={\begin{bmatrix}a_{11}&a_{12}\\a_{21}&a_{22}\end{bmatrix}}$, and ${\vec {x}}=\left\langle x_{1},x_{2}\right\rangle$.

We have ${\vec {x}}^{T}\,A\,{\vec {x}}=F(x_{1},x_{2})=a_{11}\,x_{1}^{2}+2a_{12}\,x_{1}\,x_{2}+a_{22}\,x_{2}^{2}$. If ${\vec {x}}=\left\langle 1,0\right\rangle$, then $a_{11}>0$; if ${\vec {x}}=\left\langle 0,1\right\rangle$, then $a_{22}>0$; and for any other ${\vec {x}}$, we have $a_{12}^{2}<a_{11}\,a_{12}$

For the general case, let ${\vec {x}}={\hat {e}}_{i}=\left\langle 0,0,\ldots ,1,\ldots ,0\right\rangle$. Then ${\vec {x}}^{T}\,A\,{\vec {x}}=a_{ii}$.

If ${\vec {x}}={\hat {e}}_{i}+{\hat {e}}_{j}$, then ${\vec {x}}^{T}\,A\,{\vec {x}}$ gives $\left(a_{ii}\,x_{i}+a_{ji}\,x_{j}\right)\,x_{i}+(a_{ij}\,x_{i}+a_{jj}\,x_{j})\,x_{j}=a_{ii}\,x_{i}^{2}+2a_{ij}\,x_{i}\,x_{j}+a_{jj}\,x_{j}^{2}$. This is positive if and only if the diagonal entries are positive.

To prove the final property, let $x_{i}=1$ and $x_{j}=-1$ in the previous part. Then ${\vec {x}}^{T}\,A\,{\vec {x}}=a_{ii}-2a_{ij}+a_{jj}>0$.

Now let $x_{i}=1$ and $x_{j}=1$. Then ${\vec {x}}^{T}\,A\,{\vec {x}}=a_{ii}+2a_{ij}+a_{jj}>0$.

Hence $\left|a_{ij}\right|<{\frac {a_{ii}+a_{jj}}{2}}<\max _{1\leq i\leq n}a_{ii}$

quod erat demonstrandum

These conditions are necessary, but not sufficient.

Section 7.1: Norms

In general, solving $A\,{\vec {x}}={\vec {b}}$ for ${\vec {x}}$ costs $O(n^{3})$.

If $A$ is a good matrix (not identity) positive definite, given $\epsilon >0$, find $x^{(1)},x^{(2)},\ldots ,x^{(k)}$ such that $\left|x^{(}k)-x\right|\leq \epsilon$ and $\left|A\,x^{k}-b\right|<\epsilon$

Let $V$ be a linear space (closed on addition and scalar multiplication)

Definition. $\left\|\cdot \right\|$ is a norm if:

1. $\left\|x\right\|\geq 0$ for $x\in V$
2. $\left\|\alpha \,x\right\|=\left|\alpha \right|\,\left\|x\right\|$ for all scalars $\alpha$
3. $\left\|x+y\right\|\leq \left\|x\right\|+\left\|y\right\|$.

Most important vector norms:

1. $\left\|{\vec {x}}\right\|_{\infty }=\max _{1\leq i\leq n}\left|x_{i}\right|$
2. $\left\|{\vec {x}}\right\|_{p}=\left(\sum _{i=1}^{n}\left|x_{i}\right|^{p}\right)^{\frac {1}{p}}$ for $1\leq p<\infty$