# Successive over-relaxation

In numerical linear algebra, the method of successive over-relaxation (SOR) is a variant of the Gauss–Seidel method for solving alinear system of equations, resulting in faster convergence. A similar method can be used for any slowly converging iterative process. It was devised simultaneously by David M. Young and by H. Frankel in 1950 for the purpose of automatically solving linear systems on digital computers. Over-relaxation methods had been used before the work of Young and Frankel. For instance, the method of Lewis Fry Richardson, and the methods developed by R. V. Southwell. However, these methods were designed for computation by human calculators, and they required some expertise to ensure convergence to the solution which made them inapplicable for programming on digital computers. These aspects are discussed in the thesis of David M. Young.[1]

# the Gram–Schmidt process

In mathematics, particularly linear algebra and numerical analysis, the Gram–Schmidt process is a method fororthonormalising a set of vectors in an inner product space, most commonly the Euclidean space Rn. The Gram–Schmidt process takes a finitelinearly independent set S = {v1, …, vk} for k ≤ n and generates an orthogonal setS′ = {u1, …, uk} that spans the same k-dimensional subspace of Rn as S.

The method is named after Jørgen Pedersen Gram and Erhard Schmidt but it appeared earlier in the work of Laplaceand Cauchy. In the theory of Lie group decompositions it is generalized by the Iwasawa decomposition.[1]

The application of the Gram–Schmidt process to the column vectors of a full column rank matrix yields the QR decomposition (it is decomposed into an orthogonal and a triangular matrix).

In linear algebra, a QR decomposition (also called a QR factorization) of a matrix is a decomposition of a matrix A into a product A = QR of an orthogonal matrix Q and anupper triangular matrix R. QR decomposition is often used to solve the linear least squares problem, and is the basis for a particular eigenvalue algorithm, the QR algorithm.

If A has n linearly independent columns, then the first n columns of Q form an orthonormal basis for the column space of A. More specifically, the first k columns of Q form an orthonormal basis for the span of the first k columns of A for any 1 ≤ k ≤ n.[1] The fact that any column k of A only depends on the first k columns of Q is responsible for the triangular form of R

# Complexity of Matrix Inversion

What is the computational complexity of inverting an nxn matrix? (In
general, not special cases such as a triangular matrix.)

Gaussian Elimination leads to O(n^3) complexity. The usual way to
count operations is to count one for each "division" (by a pivot) and
one for each "multiply-subtract" when you eliminate an entry.

Here's one way of arriving at the O(n^3) result:

At the beginning, when the first row has length n, it takes n
operations to zero out any entry in the first column (one division,
and n-1 multiply-subtracts to find the new entries along the row
containing that entry. To get the first column of zeroes therefore
takes n(n-1) operations.

In the next column, we need (n-1)(n-2) operations to get the second
column zeroed out.

In the third column, we need (n-2)(n-3) operations.

The sum of all of these operations is:

n            n         n      n(n+1)(2n+1)   n(n+1)
SUM i(i-1) = SUM i^2 - SUM i = ------------ - ------
i=1          i=1       i=1           6           2

which goes as O(n^3). To finish the operation count for Gaussian
Elimination, you'll need to tally up the operations for the process
of back-substitution (you can check that this doesn't affect the

You might think that the O(n^3) complexity is optimal, but in fact
there exists a method (Strassen's method) that requires only
O(n^log_2(7)) = O(n^2.807...) operations for a completely general
matrix. Of course, there is a constant C in front of the n^2.807. This
constant is not small (between 4 and 5), and the programming of
Strassen's algorithm is so awkward, that often Gaussian Elimination is
still the preferred method.

Even Strassen's method is not optimal. I believe that the current
record stands at O(n^2.376), thanks to Don Coppersmith and Shmuel
Winograd. Here is a Web page that discusses these methods:

Fast Parallel Matrix Multiplication - Strategies for Practical
Hybrid Algorithms - Erik Ehrling
http://www.f.kth.se/~f95-eeh/exjobb/background.html

These methods exploit the close relation between matrix inversion and
matrix multiplication (which is also an O(n^3) task at first glance).

I hope this helps!

- Doctor Douglas, The Math Forum
http://mathforum.org/dr.math/

# cofactor

In linear algebra, the cofactor (sometimes called adjunct, see below) describes a particular construction that is useful for calculating both the determinant and inverse of square matrices. Specifically the cofactor of the (ij) entry of a matrix, also known as the (ij) cofactor of that matrix, is the signed minor of that entry.

Finding the minors of a matrix A is a multi-step process:
1. Choose an entry aij from the matrix.
2. Cross out the entries that lie in the corresponding row i and column j.
3. Rewrite the matrix without the marked entries.
4. Obtain the determinant Mij of this new matrix.
Mij is termed the minor for entry aij.
If i + j is an even number, the cofactor Cij of aij coincides with its minor:
$C_{ij} = M_{ij}. \,$
Otherwise, it is equal to the additive inverse of its minor:
$C_{ij} = -M_{ij}. \,$
The matrix of cofactors for an $n\times n$ matrix A is the matrix whose (i,j) entry is the cofactor Cij of A. For instance, if A is
$A = \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \end{bmatrix}$
the cofactor matrix of A is
$C = \begin{bmatrix} C_{11} & C_{12} & \cdots & C_{1n} \\ C_{21} & C_{22} & \cdots & C_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ C_{n1} & C_{n2} & \cdots & C_{nn} \end{bmatrix}$
where Cij is the cofactor of aij.
In linear algebra, the Laplace expansion, named after Pierre-Simon Laplace, also called cofactor expansion, is an expression for the determinant |B| of an n × n square matrix B that is a weighted sum of the determinants of n sub-matrices of B, each of size (n–1) × (n–1). The Laplace expansion is of theoretical interest as one of several ways to view the determinant, as well as of practical use in determinant computation.
The i,j cofactor of B is the scalar Cij defined by
$C_{ij}\ = (-1)^{i+j} |M_{ij}|\,,$
where Mij is the i,j minor matrix of B, that is, the (n–1) × (n–1) matrix that results from deleting the i-th row and the j-th column of B.
Then the Laplace expansion is given by the following
Theorem. Suppose B = (bij) is an n × n matrix and i,j ∈ {1, 2, …,n}.
Then its determinant |B| is given by:
\begin{align}|B| & {} = b_{i1} C_{i1} + b_{i2} C_{i2} + \cdots + b_{in} C_{in} \\ & {} = b_{1j} C_{1j} + b_{2j} C_{2j} + \cdots + b_{nj} C_{nj}. \end{align}
Suppose R is a commutative ring and A is an n×n matrix with entries from R. The definition of the adjugate of A is a multi-step process:
• Define the (i,jminor of A, denoted Mij, as the determinant of the (n − 1)×(n − 1) matrix that results from deleting row i and column j of A.
• Define the (i,jcofactor of A as
$\mathbf{C}_{ij} = (-1)^{i+j} \mathbf{M}_{ij}. \,$
• Define the cofactor matrix of A, as the n×n matrix C whose (i,j) entry is the (i,j) cofactor of A.
The adjugate of A is the transpose of the cofactor matrix of A:
$\mathrm{adj}(\mathbf{A}) = \mathbf{C}^T \,$.
That is, the adjugate of A is the n×n matrix whose (i,j) entry is the (j,i) cofactor of A:
$\mathrm{adj}(\mathbf{A})_{ij} = \mathbf{C}_{ji} \,$.

## Examples

### 2 × 2 generic matrix

The adjugate of the 2 × 2 matrix
$\mathbf{A} = \begin{pmatrix} {{a}} & {{b}}\\ {{c}} & {{d}} \end{pmatrix}$
is
$\operatorname{adj}(\mathbf{A}) = \begin{pmatrix} \,\,\,{{d}} & \!\!{{-b}}\\ {{-c}} & {{a}} \end{pmatrix}$.

### 3 × 3 generic matrix

Consider the $3\times 3$ matrix
$\mathbf{A} = \begin{pmatrix} A_{11} & A_{12} & A_{13} \\ A_{21} & A_{22} & A_{23} \\ A_{31} & A_{32} & A_{33} \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{pmatrix}$.
Its adjugate is the transpose of the cofactor matrix
$\mathbf{C} = \begin{pmatrix} +\left| \begin{matrix} A_{22} & A_{23} \\ A_{32} & A_{33} \end{matrix} \right| & -\left| \begin{matrix} A_{21} & A_{23} \\ A_{31} & A_{33} \end{matrix} \right| & +\left| \begin{matrix} A_{21} & A_{22} \\ A_{31} & A_{32} \end{matrix} \right| \\ & & \\ -\left| \begin{matrix} A_{12} & A_{13} \\ A_{32} & A_{33} \end{matrix} \right| & +\left| \begin{matrix} A_{11} & A_{13} \\ A_{31} & A_{33} \end{matrix} \right| & -\left| \begin{matrix} A_{11} & A_{12} \\ A_{31} & A_{32} \end{matrix} \right| \\ & & \\ +\left| \begin{matrix} A_{12} & A_{13} \\ A_{22} & A_{23} \end{matrix} \right| & -\left| \begin{matrix} A_{11} & A_{13} \\ A_{21} & A_{23} \end{matrix} \right| & +\left| \begin{matrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{matrix} \right| \end{pmatrix} = \begin{pmatrix} +\left| \begin{matrix} 5 & 6 \\ 8 & 9 \end{matrix} \right| & -\left| \begin{matrix} 4 & 6 \\ 7 & 9 \end{matrix} \right| & +\left| \begin{matrix} 4 & 5 \\ 7 & 8 \end{matrix} \right| \\ & & \\ -\left| \begin{matrix} 2 & 3 \\ 8 & 9 \end{matrix} \right| & +\left| \begin{matrix} 1 & 3 \\ 7 & 9 \end{matrix} \right| & -\left| \begin{matrix} 1 & 2 \\ 7 & 8 \end{matrix} \right| \\ & & \\ +\left| \begin{matrix} 2 & 3 \\ 5 & 6 \end{matrix} \right| & -\left| \begin{matrix} 1 & 3 \\ 4 & 6 \end{matrix} \right| & +\left| \begin{matrix} 1 & 2 \\ 4 & 5 \end{matrix} \right| \end{pmatrix}$
So that we have
$\operatorname{adj}(\mathbf{A}) = \begin{pmatrix} +\left| \begin{matrix} A_{22} & A_{23} \\ A_{32} & A_{33} \end{matrix} \right| & -\left| \begin{matrix} A_{12} & A_{13} \\ A_{32} & A_{33} \end{matrix} \right| & +\left| \begin{matrix} A_{12} & A_{13} \\ A_{22} & A_{23} \end{matrix} \right| \\ & & \\ -\left| \begin{matrix} A_{21} & A_{23} \\ A_{31} & A_{33} \end{matrix} \right| & +\left| \begin{matrix} A_{11} & A_{13} \\ A_{31} & A_{33} \end{matrix} \right| & -\left| \begin{matrix} A_{11} & A_{13} \\ A_{21} & A_{23} \end{matrix} \right| \\ & & \\ +\left| \begin{matrix} A_{21} & A_{22} \\ A_{31} & A_{32} \end{matrix} \right| & -\left| \begin{matrix} A_{11} & A_{12} \\ A_{31} & A_{32} \end{matrix} \right| & +\left| \begin{matrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{matrix} \right| \end{pmatrix} = \begin{pmatrix} +\left| \begin{matrix} 5 & 6 \\ 8 & 9 \end{matrix} \right| & -\left| \begin{matrix} 2 & 3 \\ 8 & 9 \end{matrix} \right| & +\left| \begin{matrix} 2 & 3 \\ 5 & 6 \end{matrix} \right| \\ & & \\ -\left| \begin{matrix} 4 & 6 \\ 7 & 9 \end{matrix} \right| & +\left| \begin{matrix} 1 & 3 \\ 7 & 9 \end{matrix} \right| & -\left| \begin{matrix} 1 & 3 \\ 4 & 6 \end{matrix} \right| \\ & & \\ +\left| \begin{matrix} 4 & 5 \\ 7 & 8 \end{matrix} \right| & -\left| \begin{matrix} 1 & 2 \\ 7 & 8 \end{matrix} \right| & +\left| \begin{matrix} 1 & 2 \\ 4 & 5 \end{matrix} \right| \end{pmatrix}$
where
$\left| \begin{matrix} A_{im} & A_{in} \\ \,\,A_{jm} & A_{jn} \end{matrix} \right|= \det\left( \begin{matrix} A_{im} & A_{in} \\ \,\,A_{jm} & A_{jn} \end{matrix} \right)$.
Note that the adjugate is the transpose of the cofactor matrix. Thus, for instance, the (3,2) entry of the adjugate is the (2,3) cofactor of A.
The adjugate matrix is the transpose of the matrix of cofactors and is very useful due to its relation to the inverse of A.
$\mathbf{A}^{-1} = \frac{1}{\det \mathbf{A}} \mbox{adj}(\mathbf{A})$
The matrix of cofactors
$\begin{bmatrix} C_{11} & C_{12} & \cdots & C_{1n} \\ C_{21} & C_{22} & \cdots & C_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ C_{n1} & C_{n2} & \cdots & C_{nn} \end{bmatrix}$
when transposed becomes
$\mathrm{adj}(A) = \begin{bmatrix} C_{11} & C_{21} & \cdots & C_{n1} \\ C_{12} & C_{22} & \cdots & C_{n2} \\ \vdots & \vdots & \ddots & \vdots \\ C_{1n} & C_{2n} & \cdots & C_{nn} \end{bmatrix}.$

## A remark about different notations

In some books, including so the called “a bible of matrix theory”[1] instead of cofactor the term adjunct is used. Moreover, it is denoted as Aij and defined in the same way as cofactor:
$\mathbf{A}_{ij} = (-1)^{i+j} \mathbf{M}_{ij}$
Using this notation the inverse matrix is written this way:
$\mathbf{A}^{-1} = \frac{1}{\det(A)}\begin{bmatrix} A_{11} & A_{21} & \cdots & A_{n1} \\ A_{12} & A_{22} & \cdots & A_{n2} \\ \vdots & \vdots & \ddots & \vdots \\ A_{1n} & A_{2n} & \cdots & A_{nn} \end{bmatrix}$

## References

1. ^ Felix GantmacherTheory of matrices (1st ed., original language is Russian), Moscow: State Publishing House of technical and theoretical literature, 1953, p.491,
• Anton, Howard; Rorres, Chris (2005), Elementary Linear Algebra (9th ed.), John Wiley and Sons, ISBN 0-471-66959-8
http://en.wikipedia.org/wiki/Cofactor_(linear_algebra)
http://en.wikipedia.org/wiki/Laplace_expansion

# Complexity of Matrix Inversion

What is the computational complexity of inverting an nxn matrix? (In general, not special cases such as a triangular matrix.)

Gaussian Elimination leads to O(n^3) complexity. The usual way to count operations is to count one for each "division" (by a pivot) and one for each "multiply-subtract" when you eliminate an entry.Here's one way of arriving at the O(n^3) result:   At the beginning, when the first row has length n, it takes n    operations to zero out any entry in the first column (one division,    and n-1 multiply-subtracts to find the new entries along the row    containing that entry. To get the first column of zeroes therefore    takes n(n-1) operations.   In the next column, we need (n-1)(n-2) operations to get the second    column zeroed out.   In the third column, we need (n-2)(n-3) operations.   The sum of all of these operations is:         n            n         n      n(n+1)(2n+1)   n(n+1)        SUM i(i-1) = SUM i^2 - SUM i = ------------ - ------        i=1          i=1       i=1           6           2   which goes as O(n^3). To finish the operation count for Gaussian    Elimination, you'll need to tally up the operations for the process    of back-substitution (you can check that this doesn't affect the    leading order of n^3).You might think that the O(n^3) complexity is optimal, but in fact there exists a method (Strassen's method) that requires only O(n^log_2(7)) = O(n^2.807...) operations for a completely general matrix. Of course, there is a constant C in front of the n^2.807. This constant is not small (between 4 and 5), and the programming of Strassen's algorithm is so awkward, that often Gaussian Elimination is still the preferred method.Even Strassen's method is not optimal. I believe that the current record stands at O(n^2.376), thanks to Don Coppersmith and Shmuel Winograd. Here is a Web page that discusses these methods:   Fast Parallel Matrix Multiplication - Strategies for Practical    Hybrid Algorithms - Erik Ehrlinghttp://www.f.kth.se/~f95-eeh/exjobb/background.html   These methods exploit the close relation between matrix inversion and matrix multiplication (which is also an O(n^3) task at first glance). I hope this helps! - Doctor Douglas, The Math Forumhttp://mathforum.org/dr.math/

# Jacobian matrix and determinant

In vector calculus, the Jacobian matrix is the matrix of all first-order partial derivatives of a vector– or scalar-valued function with respect to another vector. Suppose F :Rn → Rm is a function from Euclidean n-space to Euclidean m-space. Such a function is given by m real-valued component functions, y1(x1,…,xn), …, ym(x1,…,xn). The partial derivatives of all these functions (if they exist) can be organized in an m-by-n matrix, the Jacobian matrix J of F, as follows:

This matrix is also denoted by  and . If (x1,…,xn) are the usual orthogonal Cartesian coordinates, the i th row (i = 1, …, m) of this matrix corresponds to the gradient of the ith component function yi. Note that some books define the Jacobian as the transpose of the matrix given above.

The Jacobian determinant (often simply called the Jacobian) is the determinant of the Jacobian matrix.

These concepts are named after the mathematician Carl Gustav Jacob Jacobi. The term “Jacobian” is normally pronounced /dʒəˈkoʊbiən/, but sometimes also /jəˈkoʊbiən/.

http://en.wikipedia.org/wiki/Jacobian_matrix_and_determinant