Orthogonal matrix - Citizendia

In matrix theory, a real orthogonal matrix is a square matrix Q whose transpose is its inverse:

$Q^T Q = Q Q^T = I . \,\!$

An orthogonal matrix is a special orthogonal matrix if its determinant is +1:

$\det Q = +1 . \,\!$

Overview

An orthogonal matrix is the real specialization of a unitary matrix, and thus always a normal matrix. Matrix theory is a branch of Mathematics which focuses on the study of matrices. In Mathematics, the real numbers may be described informally in several different ways In Mathematics, a matrix (plural matrices) is a rectangular table of elements (or entries) which may be Numbers or more generally This article is about the Matrix Transpose operator For other uses see Transposition In Linear algebra, the transpose of a In Linear algebra, an n -by- n (square matrix A is called invertible or non-singular if there exists an n -by- In Algebra, a determinant is a function depending on n that associates a scalar, det( A) to every n × n In Mathematics, a unitary matrix is an n by n complex matrix U satisfying the condition U^* U = UU^* A complex square matrix A is a normal matrix if A*A=AA* where A * is the Conjugate transpose Although we consider only real matrices here, the definition can be used for matrices with entries from any field. In Abstract algebra, a field is an Algebraic structure in which the operations of Addition, Subtraction, Multiplication and division However, orthogonal matrices arise naturally from inner products, and for matrices of complex numbers that leads instead to the unitary requirement.

To see the inner product connection, consider a vector v in an n-dimensional real inner product space. In Mathematics, an inner product space is a Vector space with the additional Structure of inner product. Written with respect to an orthonormal basis, the squared length of v is v^Tv. If a linear transformation, in matrix form Qv, preserves vector lengths, then

${\bold v}^T{\bold v} = (Q{\bold v})^T(Q{\bold v}) = {\bold v}^T Q^T Q {\bold v} .$

Thus finite-dimensional linear isometries—rotations, reflections, and their combinations—produce orthogonal matrices. In Mathematics, the dimension of a Vector space V is the cardinality (i For the Mechanical engineering and Architecture usage see Isometric projection. The converse is also true: orthogonal matrices imply orthogonal transformations. However, linear algebra includes orthogonal transformations between spaces which may be neither finite-dimensional nor of the same dimension, and these have no orthogonal matrix equivalent. Linear algebra is the branch of Mathematics concerned with In Mathematics, an inner product space is a Vector space with the additional Structure of inner product.

Orthogonal matrices are important for a number of reasons, both theoretical and practical. The n×n orthogonal matrices form a group, the orthogonal group denoted by O(n), which—with its subgroups—is widely used in mathematics and the physical sciences. In Mathematics, a group is a set of elements together with an operation that combines any two of its elements to form a third element In Mathematics, the orthogonal group of degree n over a field F (written as O( n, F) is the group of n For example, the point group of a molecule is a subgroup of O(3). In Mathematics, a point group is a group of geometric symmetries ( isometries) leaving a point fixed Because floating point versions of orthogonal matrices have advantageous properties, they are key to many algorithms in numerical linear algebra, such as QR decomposition. Linear algebra is the branch of Mathematics concerned with In Linear algebra, the QR decomposition (also called the QR factorization) of a matrix is a decomposition of the matrix into an orthogonal As another example, with appropriate normalization the discrete cosine transform (used in MP3 compression) is represented by an orthogonal matrix. A discrete cosine transform ( DCT) expresses a sequence of finitely many data points in terms of a sum of Cosine functions oscillating at different frequencies MPEG-1 Audio Layer 3, more commonly referred to as MP3, is a Digital audio encoding format using a form of Lossy data compression

Examples

Below are a few examples of small orthogonal matrices and possible interpretations.

$\begin{bmatrix} 1 & 0 \\ 0 & 1 \\ \end{bmatrix} \qquad (\text{identity transformation})$

$\begin{bmatrix} 0.96 & -0.28 \\ 0.28 & \;\;\,0.96 \\ \end{bmatrix} \qquad (\text{rotation by }16.26^{\circ})$

$\begin{bmatrix} 1 & 0 \\ 0 & -1 \\ \end{bmatrix} \qquad (\text{reflection across }x\text{-axis})$

$\begin{bmatrix} 0 & -0.80 & -0.60 \\ 0.80 & -0.36 & \;\;\,0.48 \\ 0.60 & \;\;\,0.48 & -0.64 \end{bmatrix} \qquad \left( \begin{align}&\text{rotoinversion:} \\&\text{axis }(0,-3/5,4/5),\text{ angle }90^{\circ}\end{align}\right)$

$\begin{bmatrix} 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{bmatrix} \qquad (\text{permutation of axes})$

Elementary constructions

Lower dimensions

The simplest orthogonal matrices are the 1×1 matrices [1] and [−1] which we can interpret as the identity and a reflection of the real line across the origin.

The 2×2 matrices have the form

$\begin{bmatrix} p & t\\ q & u \end{bmatrix},$

which orthogonality demands satisfy the three equations

$1 = p^2+q^2\,\! ,$

$1 = t^2+u^2\,\! ,$

$0 = pt+qu\,\! .$

In consideration of the first equation, without loss of generality let p = cos θ, q = sin θ; then either t = −q, u = p or t = q, u = −p. We can interpret the first case as a rotation by θ (where θ = 0 is the identity), and the second as a reflection across a line at an angle of θ/2.

$\begin{bmatrix} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \\ \end{bmatrix}$ (rotation), $\begin{bmatrix} \cos \theta & \sin \theta \\ \sin \theta & -\cos \theta \\ \end{bmatrix}$ (reflection)

The reflection at 45° exchanges x and y; it is a permutation matrix, with a single 1 in each column and row (and otherwise 0):

$\begin{bmatrix} 0 & 1\\ 1 & 0 \end{bmatrix}.$

The identity is also a permutation matrix. In Mathematics, in Matrix theory, a permutation matrix is a square (01-matrix that has exactly one entry 1 in each row and each column and 0's elsewhere

A reflection is its own inverse, which implies that a reflection matrix is symmetric (equal to its transpose) as well as orthogonal. In Linear algebra, a symmetric matrix is a Square matrix, A, that is equal to its Transpose A = A^{T} The product of two rotation matrices is a rotation matrix, and the product of two reflection matrices is also a rotation matrix.

Higher dimensions

Regardless of the dimension, it is always possible to classify orthogonal matrices as purely rotational or not, but for 3×3 matrices and larger the non-rotational matrices can be more complicated than reflections. For example,

$\begin{bmatrix} -1 & 0 & 0\\ 0 & -1 & 0\\ 0 & 0 & -1 \end{bmatrix}$ and $\begin{bmatrix} 0 & -1 & 0\\ 1 & 0 & 0\\ 0 & 0 & -1 \end{bmatrix}$

represent an inversion through the origin and a rotoinversion about the z axis. In Euclidean geometry, the inversion of a point X in respect to a point P is a point X * such that P is the midpoint of In 3D Geometry, an improper rotation, also called rotoreflection or rotary reflection is depending on context a Linear transformation or

Rotations also become more complicated; they can no longer be completely characterized by an angle, and may affect more than one planar subspace. While it is common to describe a 3×3 rotation matrix in terms of an axis and angle, the existence of an axis is an accidental property of this dimension that applies in no other.

However, we have elementary building blocks for permutations, reflections, and rotations that apply in general.

Primitives

The most elementary permutation is a transposition, obtained from the identity matrix by exchanging two rows. Any n×n permutation matrix can be constructed as a product of at most n−1 transpositions.

A Householder reflection is constructed from a non-null vector v as

$Q = I - 2 {{\bold v}{\bold v}^T \over {\bold v}^T{\bold v}} .$

Here the numerator is a symmetric matrix while the denominator is a number, the squared magnitude of v. In Mathematics, a Householder transformation in 3-dimensional space is the reflection of a vector in a plane. This is a reflection in the hyperplane perpendicular to v (negating any vector component parallel to v). If v is a unit vector, then Q = I−2vv^T suffices. A Householder reflection is typically used to simultaneously zero the lower part of a column. Any orthogonal matrix of size n×n can be constructed as a product of at most n such reflections.

A Givens rotation acts on a two-dimensional (planar) subspace spanned by two coordinate axes, rotating by a chosen angle. In Numerical linear algebra, a Givens rotation is a Rotation in the plane spanned by two coordinates axes It is typically used to zero a single subdiagonal entry. Any rotation matrix of size n×n can be constructed as a product of at most n(n−1)/2 such rotations. In the case of 3x3 matrices, three such rotations suffice; and by fixing the sequence we can thus describe all 3×3 rotation matrices (though not uniquely) in terms of the three angles used, often called Euler angles. The Euler angles were developed by Leonhard Euler to describe the orientation of a Rigid body (a body in which the relative position of all its points is constant

A Jacobi rotation has the same form as a Givens rotation, but is used as a similarity transformation chosen to zero both off-diagonal entries of a 2×2 symmetric submatrix. In Numerical linear algebra, a Jacobi rotation is a rotation, Q k ℓ of a 2-dimensional linear subspace of an n- dimensional In Linear algebra, two n -by- n matrices A and B over the field K are called similar if there exists

Properties

Matrix properties

A real square matrix is orthogonal if and only if its columns form an orthonormal basis of the Euclidean space Rⁿ with the ordinary Euclidean dot product, which is the case if and only if its rows form an orthonormal basis of Rⁿ. ↔ In Mathematics, an orthonormal basis of an Inner product space V (i In Mathematics, the dot product, also known as the scalar product, is an operation which takes two vectors over the Real numbers R It might be tempting to suppose a matrix with orthogonal (not orthonormal) columns would be called an orthogonal matrix, but such matrices have no special interest and no special name; they only satisfy M^TM = D, with D a diagonal matrix. In Linear algebra, a diagonal matrix is a Square matrix in which the entries outside the Main diagonal (↘ are all zero

The determinant of any orthogonal matrix is +1 or −1. In Algebra, a determinant is a function depending on n that associates a scalar, det( A) to every n × n This follows from basic facts about determinants, as follows:

$1=\det(I)=\det(Q^TQ)=\det(Q^T)\det(Q)=(\det(Q))^2\,\! .$

The converse is not true; having a determinant of +1 is no guarantee of orthogonality, even with orthogonal columns, as shown by the following counterexample.

$\begin{bmatrix} 2 & 0 \\ 0 & \frac{1}{2} \end{bmatrix}$

With permutation matrices the determinant matches the signature, being +1 or −1 as the parity of the permutation is even or odd, for the determinant is an alternating function of the rows. In Mathematics, the Permutations of a Finite set (ie the bijective mappings from the set to itself fall into two classes of equal size the even

Stronger than the determinant restriction is the fact that an orthogonal matrix can always be diagonalized over the complex numbers to exhibit a full set of eigenvalues, all of which must have (complex) absolute value 1. In Linear algebra, a Square matrix A is called diagonalizable if it is similar to a Diagonal matrix, i Complex plane In Mathematics, the complex numbers are an extension of the Real numbers obtained by adjoining an Imaginary unit, denoted In Mathematics, given a Linear transformation, an of that linear transformation is a nonzero vector which when that transformation is applied to it changes In Mathematics, the absolute value (or modulus) of a Real number is its numerical value without regard to its sign.

Group properties

The inverse of every orthogonal matrix is again orthogonal, as is the matrix product of two orthogonal matrices. In fact, the set of all n×n orthogonal matrices satisfies all the axioms of a group. In Mathematics, a group is a set of elements together with an operation that combines any two of its elements to form a third element It is a compact Lie group of dimension n(n−1)/2, called the orthogonal group and denoted by O(n). In Mathematics, a Lie group (ˈliː sounds like "Lee" is a group which is also a Differentiable manifold, with the property that the group In Mathematics, the orthogonal group of degree n over a field F (written as O( n, F) is the group of n

The orthogonal matrices whose determinant is +1 form a path-connected normal subgroup of O(n) of index 2, the special orthogonal group SO(n) of rotations. In Topology and related branches of Mathematics, a connected space is a Topological space which cannot be represented as the disjoint union of In Mathematics, more specifically in Abstract algebra, a normal subgroup is a special kind of Subgroup. In Mathematics, if G is a group, H is a Subgroup of G, and g is an element of G, then gH In Mathematics, the orthogonal group of degree n over a field F (written as O( n, F) is the group of n A rotation is a movement of an object in a circular motion A two- Dimensional object rotates around a center (or point) of rotation The quotient group O(n)/SO(n) is isomorphic to O(1), with the projection map choosing [+1] or [−1] according to the determinant. In Mathematics, given a group G and a Normal subgroup N of G, the quotient group, or factor group, of G Orthogonal matrices with determinant −1 do not include the identity, and so do not form a subgroup but only a coset; it is also (separately) connected. In Mathematics, if G is a group, H is a Subgroup of G, and g is an element of G, then gH Thus each orthogonal group falls into two pieces; and because the projection map splits, O(n) is a semidirect product of SO(n) by O(1). In Mathematics, especially in Homological algebra and other applications of Abelian category theory as well as in Differential geometry and Group In Mathematics, especially in the area of Abstract algebra known as Group theory, a semidirect product is a particular way in which a group can In practical terms, a comparable statement is that any orthogonal matrix can be produced by taking a rotation matrix and possibly negating one of its columns, as we saw with 2×2 matrices. If n is odd, then the semidirect product is in fact a direct product, and any orthogonal matrix can be produced by taking a rotation matrix and possibly negating all of its columns. In Mathematics, one can often define a direct product of objectsalready known giving a new one This follows from the property of determinants that negating a column negates the determinant, and thus negating an odd (but not even) number of columns negates the determinant.

Now consider (n+1)×(n+1) orthogonal matrices with bottom right entry equal to 1. The remainder of the last column (and last row) must be zeros, and the product of any two such matrices has the same form. The rest of the matrix is an n×n orthogonal matrix; thus O(n) is a subgroup of O(n+1) (and of all higher groups).

$\begin{bmatrix} & & & 0\\ & O(n) & & \vdots\\ & & & 0\\ 0 & \cdots & 0 & 1 \end{bmatrix}$

Since an elementary reflection in the form of a Householder matrix can reduce any orthogonal matrix to this constrained form, a series of such reflections can bring any orthogonal matrix to the identity; thus an orthogonal group is a reflection group. A reflection group is a Group action, acting on a finite dimensional Vector space, which is generated by reflections elements that fix a Hyperplane in The last column can be fixed to any unit vector, and each choice gives a different copy of O(n) in O(n+1); in this way O(n+1) is a bundle over the unit sphere Sⁿ with fiber O(n). In Mathematics, in particular in Topology, a fiber bundle (or fibre bundle) is a space which looks locally like a Product space.

Similarly, SO(n) is a subgroup of SO(n+1); and any special orthogonal matrix can be generated by Givens plane rotations using an analogous procedure. The bundle structure persists: SO(n) ↪ SO(n+1) → Sⁿ. A single rotation can produce a zero in the first row of the last column, and series of n−1 rotations will zero all but the last row of the last column of an n×n rotation matrix. Since the planes are fixed, each rotation has only one degree of freedom, its angle. By induction, SO(n) therefore has

$(n-1) + (n-2) + \cdots + 1 = n(n-1)/2$

degrees of freedom, and so does O(n).

Permutation matrices are simpler still; they form, not a Lie group, but only a finite group, the order n! symmetric group S_n. In Mathematics, the symmetric group on a set X, denoted by S X or Sym( X) is the group whose underlying By the same kind of argument, S_n is a subgroup of S_n+1. The even permutations produce the subgroup of permutation matrices of determinant +1, the order n!/2 alternating group. In Mathematics, an alternating group is the group of Even permutations of a Finite set.

Canonical form

More broadly, the effect of any orthogonal matrix separates into independent actions on orthogonal two-dimensional subspaces. That is, if Q is special orthogonal then one can always find an orthogonal matrix P, a (rotational) change of basis, that brings Q into block diagonal form:

$P^{T}QP = \begin{bmatrix} R_1 & & \\ & \ddots & \\ & & R_k \end{bmatrix}$ (n even), $P^{T}QP = \begin{bmatrix} R_1 & & & \\ & \ddots & & \\ & & R_k & \\ & & & 1 \end{bmatrix}$ (n odd).

where the matrices R₁,. . . ,R_k are 2×2 rotation matrices, and with the remaining entries zero. Exceptionally, a rotation block may be diagonal, ±I. Thus, negating one column if necessary, and noting that a 2×2 reflection diagonalizes to a +1 and −1, any orthogonal matrix can be brought to the form

$P^{T}QP = \begin{bmatrix} \begin{matrix}R_1 & & \\ & \ddots & \\ & & R_k\end{matrix} & 0 \\ 0 & \begin{matrix}\pm 1 & & \\ & \ddots & \\ & & \pm 1\end{matrix} \\ \end{bmatrix}$ ,

The matrices R₁,…,R_k give conjugate pairs of eigenvalues lying on the unit circle in the complex plane; so this decomposition confirms that all eigenvalues have absolute value 1. Complex plane In Mathematics, the complex numbers are an extension of the Real numbers obtained by adjoining an Imaginary unit, denoted In Mathematics, given a Linear transformation, an of that linear transformation is a nonzero vector which when that transformation is applied to it changes In Mathematics, the absolute value (or modulus) of a Real number is its numerical value without regard to its sign. If n is odd, there is at least one real eigenvalue, +1 or −1; for a 3×3 rotation, the eigenvector associated with +1 is the rotation axis.

Lie algebra

Suppose the entries of Q are differentiable functions of t, and that t = 0 gives Q = I. Differentiating the orthogonality condition

$Q^T Q = I \,\!$

yields

$\dot{Q}^T Q + Q^T \dot{Q} = 0$

Evaluation at t = 0 (Q = I) then implies

$\dot{Q}^T = -\dot{Q} .$

In Lie group terms, this means that the Lie algebra of an orthogonal matrix group consists of skew-symmetric matrices. In Mathematics, a Lie algebra is an algebraic structure whose main use is in studying geometric objects such as Lie groups and differentiable Manifolds Lie In Linear algebra, a skew-symmetric (or antisymmetric) matrix is a Square matrix A whose Transpose is also its negative Going the other direction, the matrix exponential of any skew-symmetric matrix is an orthogonal matrix (in fact, special orthogonal). In Mathematics, the matrix exponential is a Matrix function on square matrices analogous to the ordinary Exponential function.

For example, the three-dimensional object physics calls angular velocity is a differential rotation, thus a vector in the Lie algebra $\mathfrak{so}(3)$ tangent to SO(3). Do not confuse with Angular frequency The unit for angular velocity is rad/s Given ω = (xθ,yθ,zθ), with v = (x,y,z) a unit vector, the correct skew-symmetric matrix form of ω is

$\Omega = \begin{bmatrix} 0 & -z\theta & y\theta \\ z\theta & 0 & -x\theta \\ -y\theta & x\theta & 0 \end{bmatrix} .$

The exponential of this is the orthogonal matrix for rotation around axis v by angle θ; setting c = cos θ/2, s = sin θ/2,

$\exp(\Omega) = \begin{bmatrix} 1 - 2s^2 + 2x^2 s^2 & 2xy s^2 - 2z sc & 2xz s^2 + 2y sc\\ 2xy s^2 + 2z sc & 1 - 2s^2 + 2y^2 s^2 & 2yz s^2 - 2x sc\\ 2xz s^2 - 2y sc & 2yz s^2 + 2x sc & 1 - 2s^2 + 2z^2 s^2 \end{bmatrix} .$

Numerical linear algebra

Benefits

Numerical analysis takes advantage of many of the properties of orthogonal matrices for numerical linear algebra, and they arise naturally. Numerical analysis is the study of Algorithms for the problems of continuous mathematics (as distinguished from Discrete mathematics) Linear algebra is the branch of Mathematics concerned with For example, it is often desirable to compute an orthonormal basis for a space, or an orthogonal change of bases; both take the form of orthogonal matrices. Having determinant ±1 and all eigenvalues of magnitude 1 is of great benefit for numeric stability. In the mathematical subfield of Numerical analysis, numerical stability is a desirable property of numerical Algorithms The precise definition of stability One implication is that the condition number is 1 (which is the minimum), so errors are not magnified when multiplying with an orthogonal matrix. In Numerical analysis, the condition number associated with a problem is a measure of that problem's amenability to digital computation that is hownumerically well-conditioned Many algorithms use orthogonal matrices like Householder reflections and Givens rotations for this reason. In Mathematics, a Householder transformation in 3-dimensional space is the reflection of a vector in a plane. In Numerical linear algebra, a Givens rotation is a Rotation in the plane spanned by two coordinates axes It is also helpful that, not only is an orthogonal matrix invertible, but its inverse is available essentially free, by exchanging indices.

Permutations are essential to the success of many algorithms, including the workhorse Gaussian elimination with partial pivoting (where permutations do the pivoting). In Linear algebra, Gaussian elimination is an efficient Algorithm for solving systems of linear equations, to find the rank of a matrix The pivot or pivot element is the element of a matrix, which is selected first by an Algorithm (e However, they rarely appear explicitly as matrices; their special form allows more efficient representation, such as a list of n indices.

Likewise, algorithms using Householder and Givens matrices typically use specialized methods of multiplication and storage. For example, a Givens rotation affects only two rows of a matrix it multiplies, changing a full multiplication of order n³ to a much more efficient order n. In Mathematics, matrix multiplication is the operation of multiplying a matrix with either a scalar or another matrix When uses of these reflections and rotations introduce zeros in a matrix, the space vacated is enough to store sufficient data to reproduce the transform, and to do so robustly. (Following Stewart (1976), we do not store a rotation angle, which is both expensive and badly behaved. )

Decompositions

A number of important matrix decompositions (Golub & Van Loan, 1996) involve orthogonal matrices, including especially:

QR decomposition: M = QR, Q orthogonal, R upper triangular
Singular value decomposition: M = UΣV^T, U and V orthogonal, Σ non-negative diagonal
Spectral decomposition: S = QΛQ^T, S symmetric, Q orthogonal, Λ diagonal. In the mathematical discipline of Linear algebra, a matrix decomposition is a Factorization of a matrix into some Canonical form. In Linear algebra, the QR decomposition (also called the QR factorization) of a matrix is a decomposition of the matrix into an orthogonal In Linear algebra, the singular value decomposition ( SVD) is an important factorization of a rectangular real or complex matrix In Mathematics, particularly Linear algebra and Functional analysis, the spectral theorem is any of a number of results about Linear operators
Polar decomposition: M = QS, Q orthogonal, S symmetric non-negative definite

Examples

Consider an overdetermined system of linear equations, as might occur with repeated measurements of a physical phenomenon to compensate for experimental errors. In Mathematics, particularly in Linear algebra and Functional analysis, the polar decomposition of a matrix or Linear operator is In Mathematics, a System of linear equations is considered overdetermined if there are more equations than unknowns Write Ax = b, where A is m×n, m > n. A QR decomposition reduces A to upper triangular R. For example, if A is 5×3 then R has the form

$R = \begin{bmatrix} \star & \star & \star \\ 0 & \star & \star \\ 0 & 0 & \star \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}$

The linear least squares problem is to find the x that minimizes ‖Ax−b‖, which is equivalent to projecting b to the subspace spanned by the columns of A. Linear least squares is an important Computational problem that arises primarily in applications when it is desired to fit a linear Mathematical model to (Think of a pigeon flying over a parking lot with the sun straight overhead; its shadow hits the nearest point on the ground. ) Assuming the columns of A (and hence R) are independent, the projection solution is found from A^TAx = A^Tb. Now A^TA is square (n×n) and invertible, and also equal to R^TR. But the lower rows of zeros in R are superfluous in the product, which is thus already in lower-triangular upper-triangular factored form, as in Gaussian elimination (Cholesky decomposition). In Linear algebra, Gaussian elimination is an efficient Algorithm for solving systems of linear equations, to find the rank of a matrix In Mathematics, the Cholesky decomposition is named after André-Louis Cholesky, who found that a symmetric Positive-definite matrix can be Here orthogonality is important not only for reducing A^TA = (R^TQ^T)QR to R^TR, but also for allowing solution without magnifying numerical problems.

In the case of a linear system which is underdetermined, or an otherwise non-invertible matrix, singular value decomposition (SVD) is equally useful. In Linear algebra, an n -by- n (square matrix A is called invertible or non-singular if there exists an n -by- With A factored as UΣV^T, a satisfactory solution uses the Moore-Penrose pseudoinverse, VΣ⁺U^T, where Σ⁺ merely replaces each non-zero diagonal entry with its reciprocal. Set x to VΣ⁺U^Tb.

The case of a square invertible matrix also holds interest. Suppose, for example, that A is a 3×3 rotation matrix which has been computed as the composition of numerous twists and turns. Floating point does not match the mathematical ideal of real numbers, so A has gradually lost its true orthogonality. A Gram-Schmidt process could orthogonalize the columns, but it is not the most reliable, nor the most efficient, nor the most invariant method. In Mathematics, particularly Linear algebra and Numerical analysis, the Gram–Schmidt process is a method for orthogonalizing a set of In Linear algebra, orthogonalization is the process of finding a set of Orthogonal vectors that span a particular subspace. The polar decomposition factors a matrix into a pair, one of which is the unique closest orthogonal matrix to the given matrix, or one of the closest if the given matrix is singular. In Mathematics, particularly in Linear algebra and Functional analysis, the polar decomposition of a matrix or Linear operator is (Closeness can be measured by any matrix norm invariant under an orthogonal change of basis, such as the spectral norm or the Frobenius norm. In Mathematics, a matrix norm is a natural extension of the notion of a Vector norm to matrices. ) For a near-orthogonal matrix, rapid convergence to the orthogonal factor can be achieved by a "Newton's method" approach due to Higham (1986) (1990), repeatedly averaging the matrix with its inverse transpose. In Numerical analysis, Newton's method (also known as the Newton–Raphson method, named after Isaac Newton and Joseph Raphson) is perhaps the Dubrulle (1994) has published an accelerated method with a convenient convergence test.

For example, consider a (very!) non-orthogonal matrix for which the simple averaging algorithm takes seven steps

$\begin{bmatrix}3 & 1\\7 & 5\end{bmatrix} \rightarrow \begin{bmatrix}1.8125 & 0.0625\\3.4375 & 2.6875\end{bmatrix} \rightarrow \cdots \rightarrow \begin{bmatrix}0.8 & -0.6\\0.6 & 0.8\end{bmatrix}$

and which acceleration trims to two steps (with γ = 0. 353553, 0. 565685).

$\begin{bmatrix}3 & 1\\7 & 5\end{bmatrix} \rightarrow \begin{bmatrix}1.41421 & -1.06066\\1.06066 & 1.41421\end{bmatrix} \rightarrow \begin{bmatrix}0.8 & -0.6\\0.6 & 0.8\end{bmatrix}$

Gram-Schmidt yields an inferior solution, shown by a Frobenius distance of 8. 28659 instead of the minimum 8. 12404.

$\begin{bmatrix}3 & 1\\7 & 5\end{bmatrix} \rightarrow \begin{bmatrix}0.393919 & -0.919145\\0.919145 & 0.393919\end{bmatrix}$

Randomization

Some numerical applications, such as Monte Carlo methods and exploration of high-dimensional data spaces, require generation of uniformly distributed random orthogonal matrices. Monte Carlo methods are a class of Computational Algorithms that rely on repeated Random sampling to compute their results In Probability theory and Statistics, the continuous uniform distribution is a family of Probability distributions such that for each member of the In this context, "uniform" is defined in terms of Haar measure, which essentially requires that the distribution not change if multiplied by any freely chosen orthogonal matrix. In Mathematical analysis, the Haar measure is a way to assign an "invariant volume" to subsets of Locally compact topological groups and subsequently define It does not work to fill a matrix with independent uniformly distributed random entries and then orthogonalize it. In Probability theory, to say that two events are independent intuitively means that the occurrence of one event makes it neither more nor less probable that the other It does work to fill it with independent normally distributed random entries, then use QR decomposition. The normal distribution, also called the Gaussian distribution, is an important family of Continuous probability distributions applicable in many fields Stewart (1980) replaced this with a more efficient idea that Diaconis & Shahshahani (1987) later generalized as the "subgroup algorithm" (in which form it works just as well for permutations and rotations). To generate an (n+1)×(n+1) orthogonal matrix, take an n×n one and a uniformly distributed unit vector of dimension n+1. Construct a Householder reflection from the vector, then apply it to the smaller matrix (embedded in the larger size with a 1 in the bottom corner).

Spin and Pin

A subtle technical problem afflicts some uses of orthogonal matrices. Not only are the group components with determinant +1 and −1 not connected to each other, even the +1 component, SO(n), is not simply connected (except for SO(1), which is trivial). In Topology, a geometrical object or space is called simply connected (or 1-connected) if it is Path-connected and every path between two points can be Thus it is sometimes advantageous, or even necessary, to work with a covering group of SO(n), the spin group, Spin(n). In Mathematics, a covering space is a Topological space C which "covers" another space X by a Surjective Local homeomorphism In Mathematics the spin group Spin( n) is the double cover of the Special orthogonal group SO( n) such that there exists a Short Likewise, O(n) has covering groups, the pin groups, Pin(n). For n > 2, Spin(n) is simply connected, and thus the universal covering group for SO(n). By far the most famous example of a spin group is Spin(3), often seen in the form of unit quaternions or Pauli spin matrices. Quaternions, in Mathematics, are a non-commutative extension of Complex numbers They were first described by the Irish Mathematician The Pauli matrices are a set of 2 × 2 complex Hermitian and unitary matrices.

In peculiarly Ouroboros fashion, the Pin and Spin groups are found within Clifford algebras, which themselves can be built from orthogonal matrices. The Ouroboros (Greek grc Ουροβόρος from grc ουροβόρος όφις "tail-devouring snake" also spelled Ourorboros, Oroborus, Uroboros In Mathematics, Clifford algebras are a type of Associative algebra.

Rectangular matrices

If Q is a rectangular matrix, then the conditions Q^TQ = I and QQ^T = I are not equivalent. The condition Q^TQ = I says that the columns of Q are orthonormal. This can only happen if Q is an m×n matrix with n ≤ m. Similarly, QQ^T = I says that the rows of Q are orthonormal, which requires n ≥ m.

There is no standard terminology for these matrices. They are sometimes called "orthonormal matrices", sometimes "orthogonal matrices", and sometimes simply "matrices with orthonormal rows/columns".

References

Diaconis, Persi; Mehrdad Shahshahani (1987). In Mathematics, the orthogonal group of degree n over a field F (written as O( n, F) is the group of n In Geometry and Linear algebra, a rotation is a transformation in a plane or in space that describes the motion of a Rigid body around a fixed In Mathematics, a unitary matrix is an n by n complex matrix U satisfying the condition U^* U = UU^* In Mathematics, a symplectic matrix is a 2n × 2n matrix M (whose entries are typically either real or complex In Linear algebra, a skew-symmetric (or antisymmetric) matrix is a Square matrix A whose Transpose is also its negative Persi Warren Diaconis (born January 31, 1945) is an American Mathematician and former professional magician "The subgroup algorithm for generating uniform random variables". Prob. in Eng. and Info. Sci. 1: 15–32. ISSN 0269-9648. An International Standard Serial Number ( ISSN) is a unique eight-digit number used to identify a print or electronic Periodical publication.
Dubrulle, Augustine A. (1994). "Frobenius Iteration for the Matrix Polar Decomposition". . HP Labs Technical Report HPL-94-117
Golub, Gene H.; Charles F. Van Loan (1996). Gene Howard Golub ( February 29, 1932 &ndash November 16, 2007) Fletcher Jones Professor of Computer Science (and by courtesy of Electrical Charles Francis Van Loan is a professor of Computer science and the Joseph C Matrix Computations, 3/e, Baltimore: Johns Hopkins University Press. ISBN 978-0-8018-5414-9.
Higham, Nicholas (1986). Nicholas John Higham FRS (born Salford 25 December 1961) is a numerical analyst and Richardson Professor of Applied Mathematics at "Computing the Polar Decomposition—with Applications". SIAM J. Sci. Stat. Comput. 7 (4): 1160–1174. ISSN 0196-5204. An International Standard Serial Number ( ISSN) is a unique eight-digit number used to identify a print or electronic Periodical publication.
Higham, Nicholas; Robert Schreiber (July 1990). Nicholas John Higham FRS (born Salford 25 December 1961) is a numerical analyst and Richardson Professor of Applied Mathematics at "Fast polar decomposition of an arbitrary matrix". SIAM J. Sci. Stat. Comput. 11 (4): 648–655. ISSN 0196-5204. An International Standard Serial Number ( ISSN) is a unique eight-digit number used to identify a print or electronic Periodical publication. [1]
Stewart, G. W. (1976). "The Economical Storage of Plane Rotations". Numerische Mathematik 25 (2): 137–138. ISSN 0029-599X. An International Standard Serial Number ( ISSN) is a unique eight-digit number used to identify a print or electronic Periodical publication.
Stewart, G. W. (1980). "The Efficient Generation of Random Orthogonal Matrices with an Application to Condition Estimators". SIAM J. Numer. Anal. 17 (3): 403–409. ISSN 0036-1429. An International Standard Serial Number ( ISSN) is a unique eight-digit number used to identify a print or electronic Periodical publication.

External links

MIT Linear Algebra Lecture on Orthogonal Matrices at Google Video, from MIT OpenCourseWare

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
network: | |

Contents

Overview

Examples

Elementary constructions

Lower dimensions

Higher dimensions

Primitives

Properties

Matrix properties

Group properties

Canonical form

Lie algebra

Numerical linear algebra

Benefits

Decompositions

Examples

Randomization

Spin and Pin

Rectangular matrices

See also

References

External links