In
linear algebra
Linear algebra is the branch of mathematics concerning linear equations such as:
:a_1x_1+\cdots +a_nx_n=b,
linear maps such as:
:(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n,
and their representations in vector spaces and through matrice ...
, an orthogonal matrix, or orthonormal matrix, is a real
square matrix
In mathematics, a square matrix is a matrix with the same number of rows and columns. An ''n''-by-''n'' matrix is known as a square matrix of order Any two square matrices of the same order can be added and multiplied.
Square matrices are often ...
whose columns and rows are
orthonormal
In linear algebra, two vectors in an inner product space are orthonormal if they are orthogonal (or perpendicular along a line) unit vectors. A set of vectors form an orthonormal set if all vectors in the set are mutually orthogonal and all of ...
vectors.
One way to express this is
where is the
transpose of and is the
identity matrix
In linear algebra, the identity matrix of size n is the n\times n square matrix with ones on the main diagonal and zeros elsewhere.
Terminology and notation
The identity matrix is often denoted by I_n, or simply by I if the size is immaterial or ...
.
This leads to the equivalent characterization: a matrix is orthogonal if its transpose is equal to its
inverse
Inverse or invert may refer to:
Science and mathematics
* Inverse (logic), a type of conditional sentence which is an immediate inference made from another conditional sentence
* Additive inverse (negation), the inverse of a number that, when a ...
:
where is the inverse of .
An orthogonal matrix is necessarily invertible (with inverse ),
unitary
Unitary may refer to:
Mathematics
* Unitary divisor
* Unitary element
* Unitary group
* Unitary matrix
* Unitary morphism
* Unitary operator
* Unitary transformation
* Unitary representation In mathematics, a unitary representation of a grou ...
(), where is the
Hermitian adjoint (
conjugate transpose) of , and therefore
normal () over the
real number
In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every ...
s. The
determinant
In mathematics, the determinant is a scalar value that is a function of the entries of a square matrix. It characterizes some properties of the matrix and the linear map represented by the matrix. In particular, the determinant is nonzero if a ...
of any orthogonal matrix is either +1 or −1. As a
linear transformation, an orthogonal matrix preserves the
inner product
In mathematics, an inner product space (or, rarely, a Hausdorff pre-Hilbert space) is a real vector space or a complex vector space with an operation called an inner product. The inner product of two vectors in the space is a scalar, often ...
of vectors, and therefore acts as an
isometry
In mathematics, an isometry (or congruence, or congruent transformation) is a distance-preserving transformation between metric spaces, usually assumed to be bijective. The word isometry is derived from the Ancient Greek: ἴσος ''isos'' ...
of
Euclidean space
Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are Euclidea ...
, such as a
rotation
Rotation, or spin, is the circular movement of an object around a '' central axis''. A two-dimensional rotating object has only one possible central axis and can rotate in either a clockwise or counterclockwise direction. A three-dimensional ...
,
reflection or
rotoreflection
In geometry, an improper rotation,. also called rotation-reflection, rotoreflection, rotary reflection,. or rotoinversion is an isometry in Euclidean space that is a combination of a rotation about an axis and a reflection in a plane perpendicul ...
. In other words, it is a
unitary transformation
In mathematics, a unitary transformation is a transformation that preserves the inner product: the inner product of two vectors before the transformation is equal to their inner product after the transformation.
Formal definition
More precisely, ...
.
The set of orthogonal matrices, under multiplication, forms the
group , known as the
orthogonal group
In mathematics, the orthogonal group in dimension , denoted , is the group of distance-preserving transformations of a Euclidean space of dimension that preserve a fixed point, where the group operation is given by composing transformations. ...
. The
subgroup consisting of orthogonal matrices with determinant +1 is called the
special orthogonal group, and each of its elements is a special orthogonal matrix. As a linear transformation, every special orthogonal matrix acts as a rotation.
Overview
An orthogonal matrix is the real specialization of a unitary matrix, and thus always a
normal matrix. Although we consider only real matrices here, the definition can be used for matrices with entries from any
field. However, orthogonal matrices arise naturally from
dot product
In mathematics, the dot product or scalar productThe term ''scalar product'' means literally "product with a scalar as a result". It is also used sometimes for other symmetric bilinear forms, for example in a pseudo-Euclidean space. is an alg ...
s, and for matrices of complex numbers that leads instead to the unitary requirement. Orthogonal matrices preserve the dot product, so, for vectors and in an -dimensional real
Euclidean space
Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are Euclidea ...
where is an orthogonal matrix. To see the inner product connection, consider a vector in an -dimensional real
Euclidean space
Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are Euclidea ...
. Written with respect to an orthonormal basis, the squared length of is . If a linear transformation, in matrix form , preserves vector lengths, then
Thus
finite-dimensional
In mathematics, the dimension of a vector space ''V'' is the cardinality (i.e., the number of vectors) of a basis of ''V'' over its base field. p. 44, §2.36 It is sometimes called Hamel dimension (after Georg Hamel) or algebraic dimension to d ...
linear isometries—rotations, reflections, and their combinations—produce orthogonal matrices. 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.
Orthogonal matrices are important for a number of reasons, both theoretical and practical. The orthogonal matrices form a
group under matrix multiplication, the
orthogonal group
In mathematics, the orthogonal group in dimension , denoted , is the group of distance-preserving transformations of a Euclidean space of dimension that preserve a fixed point, where the group operation is given by composing transformations. ...
denoted by , which—with its subgroups—is widely used in mathematics and the physical sciences. For example, the
point group
In geometry, a point group is a mathematical group of symmetry operations ( isometries in a Euclidean space) that have a fixed point in common. The coordinate origin of the Euclidean space is conventionally taken to be a fixed point, and every ...
of a molecule is a subgroup of O(3). Because floating point versions of orthogonal matrices have advantageous properties, they are key to many algorithms in numerical linear algebra, such as
decomposition. As another example, with appropriate normalization the
discrete cosine transform (used in
MP3 compression) is represented by an orthogonal matrix.
Examples
Below are a few examples of small orthogonal matrices and possible interpretations.
*
(identity transformation)
*
(rotation about the origin)
*
(reflection across ''x''-axis)
*
(permutation of coordinate axes)
Elementary constructions
Lower dimensions
The simplest orthogonal matrices are the matrices
and
��1 which we can interpret as the identity and a reflection of the real line across the origin.
The matrices have the form
which orthogonality demands satisfy the three equations
In consideration of the first equation, without loss of generality let , ; then either , or , . We can interpret the first case as a rotation by (where is the identity), and the second as a reflection across a line at an angle of .
The special case of the reflection matrix with generates a reflection about the line at 45° given by and therefore exchanges and ; it is a
permutation matrix
In mathematics, particularly in matrix theory, a permutation matrix is a square binary matrix that has exactly one entry of 1 in each row and each column and 0s elsewhere. Each such matrix, say , represents a permutation of elements and, whe ...
, with a single 1 in each column and row (and otherwise 0):
The identity is also a permutation matrix.
A reflection is
its own inverse, which implies that a reflection matrix is
symmetric (equal to its transpose) as well as orthogonal. The product of two rotation matrices is a
rotation matrix In linear algebra, a rotation matrix is a transformation matrix that is used to perform a rotation in Euclidean space. For example, using the convention below, the matrix
:R = \begin
\cos \theta & -\sin \theta \\
\sin \theta & \cos \theta
\ ...
, 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 matrices and larger the non-rotational matrices can be more complicated than reflections. For example,
represent an ''
inversion
Inversion or inversions may refer to:
Arts
* , a French gay magazine (1924/1925)
* ''Inversion'' (artwork), a 2005 temporary sculpture in Houston, Texas
* Inversion (music), a term with various meanings in music theory and musical set theory
* ...
'' through the origin and a ''
rotoinversion'', respectively, about the -axis.
Rotations become more complicated in higher dimensions; they can no longer be completely characterized by one angle, and may affect more than one planar subspace. It is common to describe a rotation matrix in terms of an
axis and angle
An axis (plural ''axes'') is an imaginary line around which an object rotates or is symmetrical. Axis may also refer to:
Mathematics
* Axis of rotation: see rotation around a fixed axis
*Axis (mathematics), a designator for a Cartesian-coordinate ...
, but this only works in three dimensions. Above three dimensions two or more angles are needed, each associated with a
plane of rotation
In geometry, a plane of rotation is an abstract object used to describe or visualize rotations in space. In three dimensions it is an alternative to the axis of rotation, but unlike the axis of rotation it can be used in other dimensions, such as ...
.
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 permutation matrix can be constructed as a product of no more than transpositions.
A
Householder reflection is constructed from a non-null vector as
Here the numerator is a symmetric matrix while the denominator is a number, the squared magnitude of . This is a reflection in the hyperplane perpendicular to (negating any vector component parallel to ). If is a unit vector, then suffices. A Householder reflection is typically used to simultaneously zero the lower part of a column. Any orthogonal matrix of size can be constructed as a product of at most such reflections.
A
Givens rotation acts on a two-dimensional (planar) subspace spanned by two coordinate axes, rotating by a chosen angle. It is typically used to zero a single subdiagonal entry. Any rotation matrix of size can be constructed as a product of at most such rotations. In the case of matrices, three such rotations suffice; and by fixing the sequence we can thus describe all rotation matrices (though not uniquely) in terms of the three angles used, often called
Euler angles
The Euler angles are three angles introduced by Leonhard Euler to describe the orientation of a rigid body with respect to a fixed coordinate system.Novi Commentarii academiae scientiarum Petropolitanae 20, 1776, pp. 189–207 (E478PDF/ref>
Th ...
.
A
Jacobi rotation has the same form as a Givens rotation, but is used to zero both off-diagonal entries of a symmetric submatrix.
Properties
Matrix properties
A real square matrix is orthogonal
if and only if
In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false.
The connective is bic ...
its columns form an
orthonormal basis
In mathematics, particularly linear algebra, an orthonormal basis for an inner product space ''V'' with finite dimension is a basis for V whose vectors are orthonormal, that is, they are all unit vectors and orthogonal to each other. For examp ...
of the
Euclidean space
Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are Euclidea ...
with the ordinary Euclidean
dot product
In mathematics, the dot product or scalar productThe term ''scalar product'' means literally "product with a scalar as a result". It is also used sometimes for other symmetric bilinear forms, for example in a pseudo-Euclidean space. is an alg ...
, which is the case if and only if its rows form an orthonormal basis of . 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 , with a
diagonal matrix.
The
determinant
In mathematics, the determinant is a scalar value that is a function of the entries of a square matrix. It characterizes some properties of the matrix and the linear map represented by the matrix. In particular, the determinant is nonzero if a ...
of any orthogonal matrix is +1 or −1. This follows from basic facts about determinants, as follows:
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.
With permutation matrices the determinant matches the
signature
A signature (; from la, signare, "to sign") is a Handwriting, handwritten (and often Stylization, stylized) depiction of someone's name, nickname, or even a simple "X" or other mark that a person writes on documents as a proof of identity and ...
, being +1 or −1 as the parity of the permutation is even or odd, for the determinant is an alternating function of the rows.
Stronger than the determinant restriction is the fact that an orthogonal matrix can always be
diagonalized over the
complex number
In mathematics, a complex number is an element of a number system that extends the real numbers with a specific element denoted , called the imaginary unit and satisfying the equation i^= -1; every complex number can be expressed in the fo ...
s to exhibit a full set of
eigenvalues
In linear algebra, an eigenvector () or characteristic vector of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denote ...
, all of which must have (complex)
modulus 1.
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 orthogonal matrices satisfies all the axioms of a
group. It is a
compact
Compact as used in politics may refer broadly to a pact or treaty; in more specific cases it may refer to:
* Interstate compact
* Blood compact, an ancient ritual of the Philippines
* Compact government, a type of colonial rule utilized in Britis ...
Lie group
In mathematics, a Lie group (pronounced ) is a group that is also a differentiable manifold. A manifold is a space that locally resembles Euclidean space, whereas groups define the abstract concept of a binary operation along with the addi ...
of dimension , called the
orthogonal group
In mathematics, the orthogonal group in dimension , denoted , is the group of distance-preserving transformations of a Euclidean space of dimension that preserve a fixed point, where the group operation is given by composing transformations. ...
and denoted by .
The orthogonal matrices whose determinant is +1 form a
path-connected normal subgroup
In abstract algebra, a normal subgroup (also known as an invariant subgroup or self-conjugate subgroup) is a subgroup that is invariant under conjugation by members of the group of which it is a part. In other words, a subgroup N of the group G ...
of of
index
Index (or its plural form indices) may refer to:
Arts, entertainment, and media Fictional entities
* Index (''A Certain Magical Index''), a character in the light novel series ''A Certain Magical Index''
* The Index, an item on a Halo megastru ...
2, the
special orthogonal group of rotations. The
quotient group
A quotient group or factor group is a mathematical group obtained by aggregating similar elements of a larger group using an equivalence relation that preserves some of the group structure (the rest of the structure is "factored" out). For exam ...
is isomorphic to , with the projection map choosing
1or
��1according to the determinant. 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. Thus each orthogonal group falls into two pieces; and because the projection map
splits, is a
semidirect product
In mathematics, specifically in group theory, the concept of a semidirect product is a generalization of a direct product. There are two closely related concepts of semidirect product:
* an ''inner'' semidirect product is a particular way in wh ...
of by . 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 matrices. If is odd, then the semidirect product is in fact a
direct product
In mathematics, one can often define a direct product of objects already known, giving a new one. This generalizes the Cartesian product of the underlying sets, together with a suitably defined structure on the product set. More abstractly, one t ...
, and any orthogonal matrix can be produced by taking a rotation matrix and possibly negating all of its columns. 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 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 orthogonal matrix; thus is a subgroup of (and of all higher groups).
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. The last column can be fixed to any unit vector, and each choice gives a different copy of in ; in this way is a
bundle
Bundle or Bundling may refer to:
* Bundling (packaging), the process of using straps to bundle up items
Biology
* Bundle of His, a collection of heart muscle cells specialized for electrical conduction
* Bundle of Kent, an extra conduction path ...
over the unit sphere with fiber .
Similarly, is a subgroup of ; and any special orthogonal matrix can be generated by
Givens plane rotations using an analogous procedure. The bundle structure persists: . A single rotation can produce a zero in the first row of the last column, and series of rotations will zero all but the last row of the last column of an rotation matrix. Since the planes are fixed, each rotation has only one degree of freedom, its angle. By induction, therefore has
degrees of freedom, and so does .
Permutation matrices are simpler still; they form, not a Lie group, but only a finite group, the order
symmetric group . By the same kind of argument, is a subgroup of . The even permutations produce the subgroup of permutation matrices of determinant +1, the order
alternating group.
Canonical form
More broadly, the effect of any orthogonal matrix separates into independent actions on orthogonal two-dimensional subspaces. That is, if is special orthogonal then one can always find an orthogonal matrix , a (rotational)
change of basis, that brings into block diagonal form:
where the matrices are rotation matrices, and with the remaining entries zero. Exceptionally, a rotation block may be diagonal, . Thus, negating one column if necessary, and noting that a reflection diagonalizes to a +1 and −1, any orthogonal matrix can be brought to the form
The matrices give conjugate pairs of eigenvalues lying on the unit circle in the
complex plane
In mathematics, the complex plane is the plane formed by the complex numbers, with a Cartesian coordinate system such that the -axis, called the real axis, is formed by the real numbers, and the -axis, called the imaginary axis, is formed by the ...
; so this decomposition confirms that all
eigenvalues
In linear algebra, an eigenvector () or characteristic vector of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denote ...
have
absolute value
In mathematics, the absolute value or modulus of a real number x, is the non-negative value without regard to its sign. Namely, , x, =x if is a positive number, and , x, =-x if x is negative (in which case negating x makes -x positive), ...
1. If is odd, there is at least one real eigenvalue, +1 or −1; for a rotation, the eigenvector associated with +1 is the rotation axis.
Lie algebra
Suppose the entries of are differentiable functions of , and that gives . Differentiating the orthogonality condition
yields
Evaluation at () then implies
In Lie group terms, this means that the
Lie algebra
In mathematics, a Lie algebra (pronounced ) is a vector space \mathfrak g together with an operation called the Lie bracket, an alternating bilinear map \mathfrak g \times \mathfrak g \rightarrow \mathfrak g, that satisfies the Jacobi identi ...
of an orthogonal matrix group consists of
skew-symmetric matrices. Going the other direction, the
matrix exponential of any skew-symmetric matrix is an orthogonal matrix (in fact, special orthogonal).
For example, the three-dimensional object physics calls
angular velocity
In physics, angular velocity or rotational velocity ( or ), also known as angular frequency vector,(UP1) is a pseudovector representation of how fast the angular position or orientation of an object changes with time (i.e. how quickly an object ...
is a differential rotation, thus a vector in the Lie algebra
tangent to . Given , with being a unit vector, the correct skew-symmetric matrix form of is
The exponential of this is the orthogonal matrix for rotation around axis by angle ; setting , ,
Numerical linear algebra
Benefits
Numerical analysis
Numerical analysis is the study of algorithms that use numerical approximation (as opposed to symbolic manipulations) for the problems of mathematical analysis (as distinguished from discrete mathematics). It is the study of numerical methods ...
takes advantage of many of the properties of orthogonal matrices for numerical linear algebra, and they arise naturally. 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 generally desirable property of numerical algorithms. The precise definition of stability depends on the context. One is numerical linear algebra and the other is algorit ...
. One implication is that the
condition number
In numerical analysis, the condition number of a function measures how much the output value of the function can change for a small change in the input argument. This is used to measure how sensitive a function is to changes or errors in the inpu ...
is 1 (which is the minimum), so errors are not magnified when multiplying with an orthogonal matrix. Many algorithms use orthogonal matrices like Householder reflections and
Givens rotations for this reason. 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). However, they rarely appear explicitly as matrices; their special form allows more efficient representation, such as a list of 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
Multiplication (often denoted by the Multiplication sign, cross symbol , by the mid-line #Notation and terminology, dot operator , by juxtaposition, or, on computers, by an asterisk ) is one of the four Elementary arithmetic, elementary Op ...
of order to a much more efficient order . 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 , we do ''not'' store a rotation angle, which is both expensive and badly behaved.)
Decompositions
A number of important
matrix decompositions involve orthogonal matrices, including especially:
;
decomposition : , orthogonal, upper triangular
;
Singular value decomposition
In linear algebra, the singular value decomposition (SVD) is a factorization of a real or complex matrix. It generalizes the eigendecomposition of a square normal matrix with an orthonormal eigenbasis to any \ m \times n\ matrix. It is re ...
: , and orthogonal, diagonal matrix
;
Eigendecomposition of a symmetric matrix (decomposition according to the
spectral theorem
In mathematics, particularly linear algebra and functional analysis, a spectral theorem is a result about when a linear operator or matrix can be diagonalized (that is, represented as a diagonal matrix in some basis). This is extremely useful be ...
) : , symmetric, orthogonal, diagonal
;
Polar decomposition : , orthogonal, symmetric positive-semidefinite
Examples
Consider an
overdetermined system of linear equations
In mathematics, a system of equations is considered overdetermined if there are more equations than unknowns. An overdetermined system is almost always inconsistent (it has no solution) when constructed with random coefficients. However, an ove ...
, as might occur with repeated measurements of a physical phenomenon to compensate for experimental errors. Write , where is , .
A decomposition reduces to upper triangular . For example, if is then has the form
The
linear least squares problem is to find the that minimizes , which is equivalent to projecting to the subspace spanned by the columns of . Assuming the columns of (and hence ) are independent, the projection solution is found from . Now is square () and invertible, and also equal to . But the lower rows of zeros in are superfluous in the product, which is thus already in lower-triangular upper-triangular factored form, as in
Gaussian elimination (
Cholesky decomposition). Here orthogonality is important not only for reducing to , 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. With factored as , a satisfactory solution uses the Moore-Penrose
pseudoinverse, , where merely replaces each non-zero diagonal entry with its reciprocal. Set to .
The case of a square invertible matrix also holds interest. Suppose, for example, that is a 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 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. 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. (Closeness can be measured by any
matrix norm invariant under an orthogonal change of basis, such as the spectral norm or the Frobenius norm.) For a near-orthogonal matrix, rapid convergence to the orthogonal factor can be achieved by a "
Newton's method
In numerical analysis, Newton's method, also known as the Newton–Raphson method, named after Isaac Newton and Joseph Raphson, is a root-finding algorithm which produces successively better approximations to the roots (or zeroes) of a real- ...
" approach due to (
1990
File:1990 Events Collage.png, From left, clockwise: The 1990 FIFA World Cup is played in Italy; The Human Genome Project is launched; Voyager I takes the famous Pale Blue Dot image- speaking on the fragility of humanity on Earth, astrophysicis ...
), repeatedly averaging the matrix with its inverse transpose. has published an accelerated method with a convenient convergence test.
For example, consider a non-orthogonal matrix for which the simple averaging algorithm takes seven steps
and which acceleration trims to two steps (with = 0.353553, 0.565685).
Gram-Schmidt yields an inferior solution, shown by a Frobenius distance of 8.28659 instead of the minimum 8.12404.
Randomization
Some numerical applications, such as
Monte Carlo method
Monte Carlo methods, or Monte Carlo experiments, are a broad class of computational algorithms that rely on repeated random sampling to obtain numerical results. The underlying concept is to use randomness to solve problems that might be deter ...
s and exploration of high-dimensional data spaces, require generation of
uniformly distributed random orthogonal matrices. In this context, "uniform" is defined in terms of
Haar measure In mathematical analysis, the Haar measure assigns an "invariant volume" to subsets of locally compact topological groups, consequently defining an integral for functions on those groups.
This measure was introduced by Alfréd Haar in 1933, thou ...
, which essentially requires that the distribution not change if multiplied by any freely chosen orthogonal matrix. Orthogonalizing matrices with
independent
Independent or Independents may refer to:
Arts, entertainment, and media Artist groups
* Independents (artist group), a group of modernist painters based in the New Hope, Pennsylvania, area of the United States during the early 1930s
* Independe ...
uniformly distributed random entries does not result in uniformly distributed orthogonal matrices, but the
decomposition of independent
normally distributed random entries does, as long as the diagonal of contains only positive entries . replaced this with a more efficient idea that later generalized as the "subgroup algorithm" (in which form it works just as well for permutations and rotations). To generate an orthogonal matrix, take an one and a uniformly distributed unit vector of dimension . Construct a Householder reflection from the vector, then apply it to the smaller matrix (embedded in the larger size with a 1 at the bottom right corner).
Nearest orthogonal matrix
The problem of finding the orthogonal matrix nearest a given matrix is related to the
Orthogonal Procrustes problem. There are several different ways to get the unique solution, the simplest of which is taking the
singular value decomposition
In linear algebra, the singular value decomposition (SVD) is a factorization of a real or complex matrix. It generalizes the eigendecomposition of a square normal matrix with an orthonormal eigenbasis to any \ m \times n\ matrix. It is re ...
of and replacing the singular values with ones. Another method expresses the explicitly but requires the use of a
matrix square root
In mathematics, the square root of a matrix extends the notion of square root from numbers to matrices. A matrix is said to be a square root of if the matrix product is equal to .
Some authors use the name ''square root'' or the notation ...
:
This may be combined with the Babylonian method for extracting the square root of a matrix to give a recurrence which converges to an orthogonal matrix quadratically:
where .
These iterations are stable provided the
condition number
In numerical analysis, the condition number of a function measures how much the output value of the function can change for a small change in the input argument. This is used to measure how sensitive a function is to changes or errors in the inpu ...
of is less than three.
"Newton's Method for the Matrix Square Root"
, Nicholas J. Higham, Mathematics of Computation, Volume 46, Number 174, 1986.
Using a first-order approximation of the inverse and the same initialization results in the modified iteration:
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, , is not simply connected (except for SO(1), which is trivial). Thus it is sometimes advantageous, or even necessary, to work with a covering group of SO(''n''), the spin group
In mathematics the spin group Spin(''n'') page 15 is the double cover of the special orthogonal group , such that there exists a short exact sequence of Lie groups (when )
:1 \to \mathrm_2 \to \operatorname(n) \to \operatorname(n) \to 1.
As a ...
, . Likewise, has covering groups, the pin groups, Pin(''n''). For , is simply connected and thus the universal covering group for . By far the most famous example of a spin group is , which is nothing but , or the group of unit quaternion
In mathematics, the quaternion number system extends the complex numbers. Quaternions were first described by the Irish mathematician William Rowan Hamilton in 1843 and applied to mechanics in three-dimensional space. Hamilton defined a quater ...
s.
The Pin and Spin groups are found within Clifford algebra
In mathematics, a Clifford algebra is an algebra generated by a vector space with a quadratic form, and is a unital associative algebra. As -algebras, they generalize the real numbers, complex numbers, quaternions and several other hyperco ...
s, which themselves can be built from orthogonal matrices.
Rectangular matrices
If is not a square matrix, then the conditions and are not equivalent. The condition says that the columns of ''Q'' are orthonormal. This can only happen if is an matrix with (due to linear dependence). Similarly, says that the rows of are orthonormal, which requires .
There is no standard terminology for these matrices. They are variously called "semi-orthogonal matrices", "orthonormal matrices", "orthogonal matrices", and sometimes simply "matrices with orthonormal rows/columns".
For the case , matrices with orthonormal columns may be referred to as orthogonal k-frames and they are elements of the Stiefel manifold In mathematics, the Stiefel manifold V_k(\R^n) is the set of all orthonormal ''k''-frames in \R^n. That is, it is the set of ordered orthonormal ''k''-tuples of vectors in \R^n. It is named after Swiss mathematician Eduard Stiefel. Likewise one ...
.
See also
* Biorthogonal system
Notes
References
*
*
*
*
*
*
*
*
External links
*
Tutorial and Interactive Program on Orthogonal Matrix
{{Matrix classes
Matrices