Orthogonal Transformations and Orthogonal Matrices - Revision history

Khanh: /* Examples */

2022-01-29T22:14:07Z

Examples

Khanh: /* Numerical linear algebra */

2022-01-29T22:13:18Z

Numerical linear algebra

Khanh: /* Properties */

2022-01-29T22:07:08Z

Properties

Khanh: /* Primitives */

2022-01-29T21:56:49Z

Primitives

Khanh: /* Higher dimensions */

2022-01-29T21:53:46Z

Higher dimensions

Khanh: /* Lower dimensions */

2022-01-29T21:51:59Z

Lower dimensions

Khanh at 21:48, 29 January 2022

2022-01-29T21:48:09Z

Show changes

Khanh: Created page with "== Licensing == Content obtained and/or adapted from: * [https://en.wikipedia.org/wiki/Orthogonal_transformation Orthogonal transformation, Wikipedia] under a CC BY-SA licens..."

2022-01-29T20:11:02Z

Created page with "== Licensing == Content obtained and/or adapted from: * [https://en.wikipedia.org/wiki/Orthogonal_transformation Orthogonal transformation, Wikipedia] under a CC BY-SA licens..."

New page

== Licensing ==
Content obtained and/or adapted from:
* [https://en.wikipedia.org/wiki/Orthogonal_transformation Orthogonal transformation, Wikipedia] under a CC BY-SA license
* [https://en.wikipedia.org/wiki/Orthogonal_matrix Orthogonal matrix, Wikipedia] under a CC BY-SA license

@@ Line 298: / Line 298: @@
 \end{bmatrix}.</math>
-The linear least squares problem is to find the {{math|'''x'''}} that minimizes ||''A'''''x − b'''||, which is equivalent to projecting {{math|'''b'''}} to the subspace spanned by the columns of {{mvar|A}}. Assuming the columns of {{mvar|A}} (and hence {{mvar|R}}) are independent, the projection solution is found from {{math|1=''A''<sup>T</sup>''A'''''x''' = ''A''<sup>T</sup>'''b'''}}. Now {{math|''A''<sup>T</sup>''A''}} is square ({{math|''n'' × ''n''}}) and invertible, and also equal to {{math|''R''<sup>T</sup>''R''}}. But the lower rows of zeros in {{mvar|R}} 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 {{math|1=''A''<sup>T</sup>''A'' = (''R''<sup>T</sup>''Q''<sup>T</sup>)''QR''}} to {{math|''R''<sup>T</sup>''R''}}, but also for allowing solution without magnifying numerical problems.
+The linear least squares problem is to find the {{math|'''x'''}} that minimizes ||''A'''''x''' − '''b'''||, which is equivalent to projecting {{math|'''b'''}} to the subspace spanned by the columns of {{mvar|A}}. Assuming the columns of {{mvar|A}} (and hence {{mvar|R}}) are independent, the projection solution is found from {{math|1=''A''<sup>T</sup>''A'''''x''' = ''A''<sup>T</sup>'''b'''}}. Now {{math|''A''<sup>T</sup>''A''}} is square ({{math|''n'' × ''n''}}) and invertible, and also equal to {{math|''R''<sup>T</sup>''R''}}. But the lower rows of zeros in {{mvar|R}} 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 {{math|1=''A''<sup>T</sup>''A'' = (''R''<sup>T</sup>''Q''<sup>T</sup>)''QR''}} to {{math|''R''<sup>T</sup>''R''}}, 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 {{mvar|A}} factored as {{math|''U''Σ''V''<sup>T</sup>}}, a satisfactory solution uses the Moore-Penrose pseudoinverse, {{math|''V''Σ<sup>+</sup>''U''<sup>T</sup>}}, where {{math|Σ<sup>+</sup>}} merely replaces each non-zero diagonal entry with its reciprocal. Set {{math|'''x'''}} to {{math|''V''Σ<sup>+</sup>''U''<sup>T</sup>'''b'''}}.

@@ Line 277: / Line 277: @@
 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 {{mvar|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 {{math|''n''<sup>3</sup>}} to a much more efficient order {{mvar|n}}. 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 {{harvtxt|Stewart|1976}}, we do ''not'' store a rotation angle, which is both expensive and badly behaved.)
+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 {{math|''n''<sup>3</sup>}} to a much more efficient order {{mvar|n}}. 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 {{harv|Golub|Van Loan|1996}} involve orthogonal matrices, including especially:
+A number of important matrix decompositions (Golub & Van Loan 1996) involve orthogonal matrices, including especially:
 ;{{mvar|QR}} decomposition : {{math|1=''M'' = ''QR''}}, {{mvar|Q}} orthogonal, {{mvar|R}} upper triangular
@@ Line 298: / Line 298: @@
 \end{bmatrix}.</math>
-The linear least squares problem is to find the {{math|'''x'''}} that minimizes {{math|{{norm|''A'''''x''' − '''b'''}}}}, which is equivalent to projecting {{math|'''b'''}} to the subspace spanned by the columns of {{mvar|A}}. Assuming the columns of {{mvar|A}} (and hence {{mvar|R}}) are independent, the projection solution is found from {{math|1=''A''<sup>T</sup>''A'''''x''' = ''A''<sup>T</sup>'''b'''}}. Now {{math|''A''<sup>T</sup>''A''}} is square ({{math|''n'' × ''n''}}) and invertible, and also equal to {{math|''R''<sup>T</sup>''R''}}. But the lower rows of zeros in {{mvar|R}} 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 {{math|1=''A''<sup>T</sup>''A'' = (''R''<sup>T</sup>''Q''<sup>T</sup>)''QR''}} to {{math|''R''<sup>T</sup>''R''}}, but also for allowing solution without magnifying numerical problems.
+The linear least squares problem is to find the {{math|'''x'''}} that minimizes ||''A'''''x − b'''||, which is equivalent to projecting {{math|'''b'''}} to the subspace spanned by the columns of {{mvar|A}}. Assuming the columns of {{mvar|A}} (and hence {{mvar|R}}) are independent, the projection solution is found from {{math|1=''A''<sup>T</sup>''A'''''x''' = ''A''<sup>T</sup>'''b'''}}. Now {{math|''A''<sup>T</sup>''A''}} is square ({{math|''n'' × ''n''}}) and invertible, and also equal to {{math|''R''<sup>T</sup>''R''}}. But the lower rows of zeros in {{mvar|R}} 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 {{math|1=''A''<sup>T</sup>''A'' = (''R''<sup>T</sup>''Q''<sup>T</sup>)''QR''}} to {{math|''R''<sup>T</sup>''R''}}, 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 {{mvar|A}} factored as {{math|''U''Σ''V''<sup>T</sup>}}, a satisfactory solution uses the Moore-Penrose pseudoinverse, {{math|''V''Σ<sup>+</sup>''U''<sup>T</sup>}}, where {{math|Σ<sup>+</sup>}} merely replaces each non-zero diagonal entry with its reciprocal. Set {{math|'''x'''}} to {{math|''V''Σ<sup>+</sup>''U''<sup>T</sup>'''b'''}}.
-The case of a square invertible matrix also holds interest. Suppose, for example, that {{mvar|A}} is a {{nowrap|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 {{mvar|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. 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" approach due to {{harvtxt|Higham|1986}} (1990), repeatedly averaging the matrix with its inverse transpose. {{harvtxt|Dubrulle|1994}} has published an accelerated method with a convenient convergence test.
+The case of a square invertible matrix also holds interest. Suppose, for example, that {{mvar|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 {{mvar|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. 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" approach due to Higham (1986) (1990), repeatedly averaging the matrix with its inverse transpose. Dubrulle (1994) 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

@@ Line 189: / Line 189: @@
 ===Matrix properties===
-A real square matrix is orthogonal [[if and only if]] its columns form an orthonormal basis of the Euclidean space {{math|'''R'''<sup>''n''</sup>}} with the ordinary Euclidean dot product, which is the case if and only if its rows form an orthonormal basis of {{math|'''R'''<sup>''n''</sup>}}. 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 {{math|1=''M''<sup>T</sup>''M'' = ''D''}}, with {{mvar|D}} a diagonal matrix.
+A real square matrix is orthogonal if and only if its columns form an orthonormal basis of the Euclidean space {{math|'''R'''<sup>''n''</sup>}} with the ordinary Euclidean dot product, which is the case if and only if its rows form an orthonormal basis of {{math|'''R'''<sup>''n''</sup>}}. 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 {{math|1=''M''<sup>T</sup>''M'' = ''D''}}, with {{mvar|D}} a diagonal matrix.
 The determinant of any orthogonal matrix is +1 or −1. This follows from basic facts about determinants, as follows:
@@ Line 205: / Line 205: @@
 ===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 {{math|''n'' × ''n''}} orthogonal matrices satisfies all the axioms of a group. It is a compact Lie group of dimension {{math|{{sfrac|''n''(''n'' − 1)|2}}}}, called the orthogonal group and denoted by {{math|O(''n'')}}.
+The inverse of every orthogonal matrix is again orthogonal, as is the matrix product of two orthogonal matrices. In fact, the set of all {{math|''n'' × ''n''}} orthogonal matrices satisfies all the axioms of a group. It is a compact Lie group of dimension <math> \tfrac{n(n-1)}{2}</math>, called the orthogonal group and denoted by {{math|O(''n'')}}.
 The orthogonal matrices whose determinant is +1 form a path-connected normal subgroup of {{math|O(''n'')}} of index 2, the special orthogonal group {{math|SO(''n'')}} of rotations. The quotient group {{math|O(''n'')/SO(''n'')}} is isomorphic to {{math|O(1)}}, with the projection map choosing [+1] or [−1] according 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, {{math|O(''n'')}} is a semidirect product of {{math|SO(''n'')}} by {{math|O(1)}}. 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 {{mvar|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. 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.
@@ Line 224: / Line 224: @@
 degrees of freedom, and so does {{math|O(''n'')}}.
-Permutation matrices are simpler still; they form, not a Lie group, but only a finite group, the order {{math|''n''!}} symmetric group {{math|S<sub>''n''</sub>}}. By the same kind of argument, {{math|S<sub>''n''</sub>}} is a subgroup of {{math|S<sub>''n'' + 1</sub>}}. The even permutations produce the subgroup of permutation matrices of determinant +1, the order {{math|{{sfrac|''n''!|2}}}} alternating group.
+Permutation matrices are simpler still; they form, not a Lie group, but only a finite group, the order {{math|''n''!}} symmetric group {{math|S<sub>''n''</sub>}}. By the same kind of argument, {{math|S<sub>''n''</sub>}} is a subgroup of {{math|S<sub>''n'' + 1</sub>}}. The even permutations produce the subgroup of permutation matrices of determinant +1, the order <math>\frac{n!}{2}</math> alternating group.
 ===Canonical form===
@@ Line 263: / Line 263: @@
 \end{bmatrix} .</math>
-The exponential of this is the orthogonal matrix for rotation around axis {{math|'''v'''}} by angle {{mvar|θ}}; setting {{math|1=''c'' = cos {{sfrac|''θ''|2}}}}, {{math|1=''s'' = sin {{sfrac|''θ''|2}}}},
+The exponential of this is the orthogonal matrix for rotation around axis {{math|'''v'''}} by angle {{mvar|θ}}; setting <math> c = cos \tfrac{\theta}{2}</math>, <math>s = sin \tfrac{\theta}{2}</math>,
 <math display="block">\exp(\Omega) = \begin{bmatrix}
   -  2s^2  +  2x^2 s^2  &  2xy s^2  -  2z sc  &  2xz s^2  +  2y sc\\

@@ Line 180: / Line 180: @@
 <math display="block">Q = I - 2 \frac{{\mathbf v}{\mathbf v}^\mathrm{T}}{{\mathbf v}^\mathrm{T}{\mathbf v}} .</math>
-Here the numerator is a symmetric matrix while the denominator is a number, the squared magnitude of {{math|'''v'''}}. This is a reflection in the hyperplane perpendicular to {{math|'''v'''}} (negating any vector component parallel to {{math|'''v'''}}). If {{math|'''v'''}} is a unit vector, then {{math|1=''Q'' = ''I'' − 2'''vv'''<sup>T</sup>}} suffices. A Householder reflection is typically used to simultaneously zero the lower part of a column. Any orthogonal matrix of size {{nowrap|''n'' × ''n''}} can be constructed as a product of at most {{mvar|n}} such reflections.
+Here the numerator is a symmetric matrix while the denominator is a number, the squared magnitude of {{math|'''v'''}}. This is a reflection in the hyperplane perpendicular to {{math|'''v'''}} (negating any vector component parallel to {{math|'''v'''}}). If {{math|'''v'''}} is a unit vector, then {{math|1=''Q'' = ''I'' − 2'''vv'''<sup>T</sup>}} 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 {{mvar|n}} 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 {{math|''n'' × ''n''}} can be constructed as a product of at most {{math|{{sfrac|''n''(''n'' − 1)|2}}}} such rotations. In the case of 3 × 3 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.
+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 <math>n \times n</math> can be constructed as a product of at most <math> \tfrac{n(n-1)}{2}</math> such rotations. In the case of 3 × 3 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.
 A Jacobi rotation has the same form as a Givens rotation, but is used to zero both off-diagonal entries of a 2 × 2 symmetric submatrix.

@@ Line 155: / Line 155: @@
 ===Higher dimensions===
-Regardless of the dimension, it is always possible to classify orthogonal matrices as purely rotational or not, but for {{nowrap|3 × 3}} matrices and larger the non-rotational matrices can be more complicated than reflections. For example,
+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,
 <math display="block">
 \begin{bmatrix}

@@ Line 131: / Line 131: @@
 \end{align}</math>
-In consideration of the first equation, without loss of generality let {{math|1=''p'' = cos ''θ''}}, {{math|1=''q'' = sin ''θ''}}; then either {{math|1=''t'' = −''q''}}, {{math|1=''u'' = ''p''}} or {{math|1=''t'' = ''q''}}, {{math|1=''u'' = −''p''}}. We can interpret the first case as a rotation by {{mvar|θ}} (where {{math|1=''θ'' = 0}} is the identity), and the second as a reflection across a line at an angle of {{math|{{sfrac|''θ''|2}}}}.
+In consideration of the first equation, without loss of generality let {{math|1=''p'' = cos ''θ''}}, {{math|1=''q'' = sin ''θ''}}; then either {{math|1=''t'' = −''q''}}, {{math|1=''u'' = ''p''}} or {{math|1=''t'' = ''q''}}, {{math|1=''u'' = −''p''}}. We can interpret the first case as a rotation by {{mvar|θ}} (where {{math|1=''θ'' = 0}} is the identity), and the second as a reflection across a line at an angle of <math> \tfrac{\theta}{2}</math>.
 <math display="block">
@@ Line 144: / Line 144: @@
 </math>
-The special case of the reflection matrix with {{math|1=''θ'' = 90°}} generates a reflection about the line at 45° given by {{math|1=''y'' = ''x''}} and therefore exchanges {{mvar|x}} and {{mvar|y}}; it is a [[permutation matrix]], with a single 1 in each column and row (and otherwise 0):
+The special case of the reflection matrix with {{math|1=''θ'' = 90°}} generates a reflection about the line at 45° given by {{math|1=''y'' = ''x''}} and therefore exchanges {{mvar|x}} and {{mvar|y}}; it is a permutation matrix, with a single 1 in each column and row (and otherwise 0):
 <math display="block">\begin{bmatrix}
 & 1\\