§3.2 Linear Algebra

To solve the system

3.2.1		$$\mathbf{A}\mathbf{x}=\mathbf{b},$$
ⓘ Referenced by: §3.2(iii), §3.2(iii) Permalink: http://dlmf.nist.gov/3.2.E1 Encodings: TeX, pMML, png See also: Annotations for §3.2(i), §3.2 and Ch.3

with Gaussian elimination, where $\mathbf{A}$ is a nonsingular $n\times n$ matrix and $\mathbf{b}$ is an $n\times 1$ vector, we start with the augmented matrix

3.2.2
ⓘ Permalink: http://dlmf.nist.gov/3.2.E2 Encodings: TeX, pMML, png See also: Annotations for §3.2(i), §3.2 and Ch.3

By repeatedly subtracting multiples of each row from the subsequent rows we obtain a matrix of the form

3.2.3
ⓘ Referenced by: §3.2(i) Permalink: http://dlmf.nist.gov/3.2.E3 Encodings: TeX, pMML, png See also: Annotations for §3.2(i), §3.2 and Ch.3

During this reduction process we store the multipliers ${\mathrm{\ell }}_{jk}$ that are used in each column to eliminate other elements in that column. This yields a lower triangular matrix of the form

3.2.4
ⓘ Symbols: ${\mathrm{\ell }}_{jk}$: multipliers Permalink: http://dlmf.nist.gov/3.2.E4 Encodings: TeX, pMML, png See also: Annotations for §3.2(i), §3.2 and Ch.3

If we denote by $\mathbf{U}$ the upper triangular matrix comprising the elements $u_{jk}$ in (3.2.3), then we have the factorization, or triangular decomposition,

3.2.5		$$\mathbf{A}=\mathbf{L}\mathbf{U}.$$
ⓘ Referenced by: §3.2(i), §3.2(ii) Permalink: http://dlmf.nist.gov/3.2.E5 Encodings: TeX, pMML, png See also: Annotations for §3.2(i), §3.2 and Ch.3

With $\mathbf{y}={[y_1,y_2,\mathrm{\dots },y_n]}^{\mathrm{T}}$ the process of solution can then be regarded as first solving the equation $\mathbf{L}\mathbf{y}=\mathbf{b}$ for $\mathbf{y}$ (forward elimination), followed by the solution of $\mathbf{U}\mathbf{x}=\mathbf{y}$ for $\mathbf{x}$ (back substitution).

For more details see Golub and Van Loan (1996, pp. 87–100).

Tridiagonal matrices are ones in which the only nonzero elements occur on the main diagonal and two adjacent diagonals. Thus

3.2.7
ⓘ Permalink: http://dlmf.nist.gov/3.2.E7 Encodings: TeX, pMML, png See also: Annotations for §3.2(ii), §3.2 and Ch.3

Assume that $\mathbf{A}$ can be factored as in (3.2.5), but without partial pivoting. Then

3.2.8
ⓘ Defines: ${\mathrm{\ell }}_{jk}$: elements of $\mathbf{L}$ (locally) Permalink: http://dlmf.nist.gov/3.2.E8 Encodings: TeX, pMML, png See also: Annotations for §3.2(ii), §3.2 and Ch.3

3.2.9
ⓘ Defines: $u_j$: elements (locally) Symbols: $d_j$: coefficient Permalink: http://dlmf.nist.gov/3.2.E9 Encodings: TeX, pMML, png See also: Annotations for §3.2(ii), §3.2 and Ch.3

where $u_j=c_j$, $j=1,2,\mathrm{\dots },n-1$, $d_1=b_1$, and

3.2.10		${\mathrm{\ell }}_j$	$=a_j/d_{j-1},$
		$d_j$	$=b_j-{\mathrm{\ell }}_j{c}_{j-1}$,
	$j=2,\mathrm{\dots },n$.
ⓘ Defines: $d_j$: coefficient (locally) Symbols: ${\mathrm{\ell }}_{jk}$: elements of $\mathbf{L}$ Permalink: http://dlmf.nist.gov/3.2.E10 Encodings: TeX, TeX, pMML, pMML, png, png See also: Annotations for §3.2(ii), §3.2 and Ch.3

Forward elimination for solving $\mathbf{A}\mathbf{x}=\mathbf{f}$ then becomes $y_1=f_1$,

3.2.11		$$y_j=f_j-{\mathrm{\ell }}_j{y}_{j-1},$$
$j=2,\mathrm{\dots },n$,
ⓘ Symbols: ${\mathrm{\ell }}_{jk}$: elements of $\mathbf{L}$ and $f_{\mathrm{i}}$: element Permalink: http://dlmf.nist.gov/3.2.E11 Encodings: TeX, pMML, png See also: Annotations for §3.2(ii), §3.2 and Ch.3

and back substitution is $x_n=y_n/d_n$, followed by

3.2.12		$$x_j=(y_j-u_j{x}_{j+1})/d_j,$$
$j=n-1,\mathrm{\dots },1$.
ⓘ Symbols: $u_j$: elements and $d_j$: coefficient Permalink: http://dlmf.nist.gov/3.2.E12 Encodings: TeX, pMML, png See also: Annotations for §3.2(ii), §3.2 and Ch.3

For more information on solving tridiagonal systems see Golub and Van Loan (1996, pp. 152–160).

The $p$-norm of a vector $\mathbf{x}={[x_1,\mathrm{\dots },x_n]}^{\mathrm{T}}$ is given by

3.2.13		${\parallel \mathbf{x}\parallel }_p$	$={\left({\displaystyle \sum _{j=1}^n}{\left|x_j\right|}^p\right)}^{1/p},$
	$p=1,2,\mathrm{\dots }$,
		${\parallel \mathbf{x}\parallel }_{\mathrm{\infty }}$	$=\underset{1\le j\le n}{\max }\left|x_j\right|.$
ⓘ Referenced by: §3.2(iv) Permalink: http://dlmf.nist.gov/3.2.E13 Encodings: TeX, TeX, pMML, pMML, png, png See also: Annotations for §3.2(iii), §3.2 and Ch.3

The Euclidean norm is the case $p=2$.

The $p$-norm of a matrix $\mathbf{A}=[a_{jk}]$ is

3.2.14		$${\parallel \mathbf{A}\parallel }_p=\underset{\mathbf{x}\ne \mathbf{0}}{\max }\frac{{\parallel \mathbf{A}\mathbf{x}\parallel }_p}{{\parallel \mathbf{x}\parallel }_p}.$$
ⓘ Referenced by: §3.2(iii) Permalink: http://dlmf.nist.gov/3.2.E14 Encodings: TeX, pMML, png See also: Annotations for §3.2(iii), §3.2 and Ch.3

The cases $p=1,2$, and $\mathrm{\infty }$ are the most important:

3.2.15		${\parallel \mathbf{A}\parallel }_1$	$=\underset{1\le k\le n}{\max }{\displaystyle \sum _{j=1}^n}\left|a_{jk}\right|,$
		${\parallel \mathbf{A}\parallel }_{\mathrm{\infty }}$	$=\underset{1\le j\le n}{\max }{\displaystyle \sum _{k=1}^n}\left|a_{jk}\right|,$
		${\parallel \mathbf{A}\parallel }_2$	$=\sqrt{\rho (\mathbf{A}{\mathbf{A}}^{\mathrm{T}})},$
ⓘ Permalink: http://dlmf.nist.gov/3.2.E15 Encodings: TeX, TeX, TeX, pMML, pMML, pMML, png, png, png See also: Annotations for §3.2(iii), §3.2 and Ch.3

where $\rho (\mathbf{A}{\mathbf{A}}^{\mathrm{T}})$ is the largest of the absolute values of the eigenvalues of the matrix $\mathbf{A}{\mathbf{A}}^{\mathrm{T}}$; see §3.2(iv). (We are assuming that the matrix $\mathbf{A}$ is real; if not ${\mathbf{A}}^{\mathrm{T}}$ is replaced by ${\mathbf{A}}^{\mathrm{H}}$, the transpose of the complex conjugate of $\mathbf{A}$.)

The sensitivity of the solution vector $\mathbf{x}$ in (3.2.1) to small perturbations in the matrix $\mathbf{A}$ and the vector $\mathbf{b}$ is measured by the condition number

3.2.16		$$\kappa (\mathbf{A})={\parallel \mathbf{A}\parallel }_p{\parallel {\mathbf{A}}^{-1}\parallel }_p,$$
ⓘ Defines: $\kappa (\mathbf{A})$: condition number (locally) Permalink: http://dlmf.nist.gov/3.2.E16 Encodings: TeX, pMML, png See also: Annotations for §3.2(iii), §3.2 and Ch.3

where ${\parallel \mathrm{\cdot }\parallel }_p$ is one of the matrix norms. For any norm (3.2.14) we have $\kappa (\mathbf{A})\ge 1$. The larger the value $\kappa (\mathbf{A})$, the more ill-conditioned the system.

Let ${\mathbf{x}}^{*}$ denote a computed solution of the system (3.2.1), with $\mathbf{r}=\mathbf{b}-\mathbf{A}{\mathbf{x}}^{*}$ again denoting the residual. Then we have the a posteriori error bound

3.2.17		$$\frac{{\parallel {\mathbf{x}}^{*}-\mathbf{x}\parallel }_p}{{\parallel \mathbf{x}\parallel }_p}\le \kappa (\mathbf{A})\frac{{\parallel \mathbf{r}\parallel }_p}{{\parallel \mathbf{b}\parallel }_p}.$$
ⓘ Symbols: $\kappa (\mathbf{A})$: condition number Permalink: http://dlmf.nist.gov/3.2.E17 Encodings: TeX, pMML, png See also: Annotations for §3.2(iii), §3.2 and Ch.3

For further information see Brezinski (1999) and Trefethen and Bau (1997, Chapter 3).

If $\mathbf{A}$ is an $n\times n$ matrix, then a real or complex number $\lambda$ is called an eigenvalue of $\mathbf{A}$, and a nonzero vector $\mathbf{x}$ a corresponding (right) eigenvector, if

3.2.18		$$\mathbf{A}\mathbf{x}=\lambda \mathbf{x}.$$
ⓘ Symbols: $\lambda$: eigenvalue Permalink: http://dlmf.nist.gov/3.2.E18 Encodings: TeX, pMML, png See also: Annotations for §3.2(iv), §3.2 and Ch.3

A nonzero vector $\mathbf{y}$ is called a left eigenvector of $\mathbf{A}$ corresponding to the eigenvalue $\lambda$ if ${\mathbf{y}}^{\mathrm{T}}\mathbf{A}=\lambda {\mathbf{y}}^{\mathrm{T}}$ or, equivalently, ${\mathbf{A}}^{\mathrm{T}}\mathbf{y}=\lambda \mathbf{y}$. A normalized eigenvector has Euclidean norm 1; compare (3.2.13) with $p=2$.

The polynomial

3.2.19		$$p_n(\lambda )=det[\lambda \mathbf{I}-\mathbf{A}]$$
ⓘ Symbols: $det$: determinant and $\lambda$: eigenvalue Permalink: http://dlmf.nist.gov/3.2.E19 Encodings: TeX, pMML, png See also: Annotations for §3.2(iv), §3.2 and Ch.3

is called the characteristic polynomial of $\mathbf{A}$ and its zeros are the eigenvalues of $\mathbf{A}$. The multiplicity of an eigenvalue is its multiplicity as a zero of the characteristic polynomial (§3.8(i)). To an eigenvalue of multiplicity $m$, there correspond $m$ linearly independent eigenvectors provided that $\mathbf{A}$ is nondefective, that is, $\mathbf{A}$ has a complete set of $n$ linearly independent eigenvectors.

If $\mathbf{A}$ is nondefective and $\lambda$ is a simple zero of $p_n(\lambda )$, then the sensitivity of $\lambda$ to small perturbations in the matrix $\mathbf{A}$ is measured by the condition number

3.2.20		$$\kappa (\lambda )=\frac{1}{\left|{\mathbf{y}}^{\mathrm{T}}\mathbf{x}\right|},$$
ⓘ Symbols: $\kappa (\mathbf{A})$: condition number and $\lambda$: eigenvalue Permalink: http://dlmf.nist.gov/3.2.E20 Encodings: TeX, pMML, png See also: Annotations for §3.2(v), §3.2 and Ch.3

where $\mathbf{x}$ and $\mathbf{y}$ are the normalized right and left eigenvectors of $\mathbf{A}$ corresponding to the eigenvalue $\lambda$. Because $\left|{\mathbf{y}}^{\mathrm{T}}\mathbf{x}\right|=\left|\cos \theta \right|$, where $\theta$ is the angle between ${\mathbf{y}}^{\mathrm{T}}$ and $\mathbf{x}$ we always have $\kappa (\lambda )\ge 1$. When $\mathbf{A}$ is a symmetric matrix, the left and right eigenvectors coincide, yielding $\kappa (\lambda )=1$, and the calculation of its eigenvalues is a well-conditioned problem.

Let $\mathbf{A}$ be an $n\times n$ symmetric matrix. Define the Lanczos vectors ${\mathbf{v}}_j$ and coefficients ${\alpha }_j$ and ${\beta }_j$ by ${\mathbf{v}}_0=\mathbf{0}$, a normalized vector ${\mathbf{v}}_1$ (perhaps chosen randomly), ${\alpha }_1={\mathbf{v}}_1^{\mathrm{T}}\mathbf{A}{\mathbf{v}}_1$, ${\beta }_1=0$, and for $j=1,2,\mathrm{\dots },n-1$ by the recursive scheme

3.2.21		$\mathbf{u}$	$=\mathbf{A}{\mathbf{v}}_j-{\alpha }_j{\mathbf{v}}_j-{\beta }_j{\mathbf{v}}_{j-1},$
		${\beta }_{j+1}$	$={\parallel \mathbf{u}\parallel }_2,$
		${\mathbf{v}}_{j+1}$	$=\mathbf{u}/{\beta }_{j+1},$
		${\alpha }_{j+1}$	$={\mathbf{v}}_{j+1}^{\mathrm{T}}\mathbf{A}{\mathbf{v}}_{j+1}.$
ⓘ Defines: ${\alpha }_j$: matrix (locally) and ${\beta }_j$: matrix (locally) Referenced by: §3.2(vi), §3.2(vi) Permalink: http://dlmf.nist.gov/3.2.E21 Encodings: TeX, TeX, TeX, TeX, pMML, pMML, pMML, pMML, png, png, png, png Modification (effective with 1.1.0): This equation has been modified to make the recursion scheme more clear to the user. See also: Annotations for §3.2(vi), §3.2 and Ch.3

Then ${\mathbf{v}}_j^{\mathrm{T}}{\mathbf{v}}_k={\delta }_{j,k}$, $j,k=1,2,\mathrm{\dots },n$. The tridiagonal matrix

3.2.22
ⓘ Symbols: ${\alpha }_j$: matrix and ${\beta }_j$: matrix Referenced by: §3.2(vi) Permalink: http://dlmf.nist.gov/3.2.E22 Encodings: TeX, pMML, png See also: Annotations for §3.2(vi), §3.2 and Ch.3

has the same eigenvalues as $\mathbf{A}$. Its characteristic polynomial can be obtained from the recursion

3.2.23		$$p_{k+1}(\lambda )=(\lambda -{\alpha }_{k+1})p_k(\lambda )-{\beta }_{k+1}^2{p}_{k-1}(\lambda ),$$
$k=0,1,\mathrm{\dots },n-1$,
ⓘ Defines: $p_k(\lambda )$: characteristic polynomial (locally) Symbols: ${\alpha }_j$: matrix, ${\beta }_j$: matrix and $\lambda$: eigenvalue Referenced by: §3.2(vi) Permalink: http://dlmf.nist.gov/3.2.E23 Encodings: TeX, pMML, png See also: Annotations for §3.2(vi), §3.2 and Ch.3

with $p_{-1}(\lambda )=0$, $p_0(\lambda )=1$.

For numerical information see Stewart (2001, pp. 347–368).

Lanczos’ method is related to Gauss quadrature considered in §3.5(v). When the matrix $\mathbf{A}$ is replaced by a scalar $x$, the recurrence relation in the first line of (3.2.21) with $\mathbf{u}={\beta }_{j+1}{\mathbf{v}}_{j+1}$ is similar to the one in (3.5.30_5). Also, the recurrence relations in (3.2.23) and (3.5.30) are similar, as well as the matrix $\mathbf{B}$ in (3.2.22) and the Jacobi matrix ${\mathbf{J}}_n$ in (3.5.31).

Many methods are available for computing eigenvalues; see Golub and Van Loan (1996, Chapters 7, 8), Trefethen and Bau (1997, Chapter 5), and Wilkinson (1988, Chapters 8, 9).