Question

Let \(B\) be any real, nonsingular \(n \times n\) matrix, where \(n\) is even, and set \(A=B-B^{T}\). Show that \(A\) does not admit an LU decomposition (i.e., some pivoting must be applied, even if \(A\) is nonsingular).

Short answer

Answer: No, matrix A does not admit an LU decomposition without pivoting.

Step-by-step solution

Define A and LU decomposition

Remember that matrix A is given by the difference between matrix B and its transpose, i.e., \(A = B - B^T\). Also, recall that an LU decomposition of a matrix consists of two matrices L (lower triangular) and U (upper triangular) such that \(A = LU\).

If A is decomposed into LU

Assume that the decomposition of A into L and U exists. Then, we have \(A = LU\), which implies that \(LU = B - B^T\).

Consider the transpose of the LU decomposition

Take the transpose of each side of the equation: \((LU)^T = (B - B^T)^T\). Since the transpose of a product is the product of transposes in reverse order, \((LU)^T = U^T L^T\). Also, \((B - B^T)^T = B^T - B\). Now, our equation becomes: \(U^T L^T = B^T - B\)

Add both equations

Let's add the initial decomposiiton equation (\(LU = B - B^T\)) to the derived equation (\(U^T L^T = B^T - B\)) to get the relationship between L and U: \((LU) + (U^T L^T) = (B - B^T) + (B^T - B)\) \(LU + U^T L^T = 0\)

Analyze the result

Since B is nonsingular, its inverse exists. Further, since B is a real matrix, it has a real transpose. Therefore, A is a real, antisymmetric matrix (\(A^T = -A\)). However, the decomposition result \(LU + U^T L^T = 0\) shows that L and U, which consist of nonzero elements (since they are triangular matrices), cancel each other out when added. This implies that LU has symmetric properties, contradicting the fact that A is antisymmetric.

Conclusion

The contradiction between the properties of A and the derived decomposition implies that our initial assumption of an LU decomposition for A is incorrect. Therefore, A does not admit an LU decomposition without pivoting.

Key concepts

Antisymmetric Matrix

An antisymmetric matrix is an interesting special type of square matrix. For any square matrix \( A \), it is considered antisymmetric if it satisfies the condition \( A^T = -A \). This implies that if you transpose the matrix, which means swapping its rows and columns, you'll get the negative of the original matrix. One simple property of antisymmetric matrices is that all their diagonal elements must be zero.
This is because when you take the transpose, diagonal elements stay unchanged, and for them to satisfy \( A^T = -A \), they must be zero. Antisymmetric matrices often appear in various areas of mathematics and physics, including representations of certain types of symmetries and forces.
In the context of LU Decomposition, when a matrix is antisymmetric, certain unexpected complications can arise, especially relating to finding direct decompositions.

Nonsingular Matrix

A nonsingular matrix, also known as an invertible or non-degenerate matrix, is a square matrix that has an inverse. In other words, a matrix \( B \) is nonsingular if there exists another matrix \( B^{-1} \) such that \( BB^{-1} = B^{-1}B = I \), where \( I \) is the identity matrix.

• The determinant of a nonsingular matrix is always non-zero.
• A nonsingular matrix always represents a linear transformation that is bijective, meaning it can be reversed.
• It has full rank, which means its rows (and columns) are linearly independent.

In the scenario of LU Decomposition, dealing with a nonsingular matrix ensures that solutions to linear systems are well-defined and unique. However, as seen in the exercise, even with a nonsingular matrix, decomposing into LU can still present challenges when the matrix is antisymmetric. This is often resolved using pivoting techniques.

Pivoting

Pivoting is an important process used in matrix decompositions, especially in LU Decomposition, to improve numerical stability and handle special cases like zeros or very small numbers on the diagonal. The primary types of pivoting are:

• Partial Pivoting: Swaps the rows to place the largest absolute value available from a column in the diagonal position.
• Complete Pivoting: Involves both row and column swaps to place the largest available number in the pivot position, although it's computationally more expensive than partial pivoting.

In the context of the given exercise, the matrix \( A = B - B^T \) being antisymmetric means it cannot directly undergo a simple LU decomposition without pivoting. Instead, pivoting needs to be applied to help manage the inherent instability and symmetry issues, ensuring that LU decomposition can proceed efficiently and accurately.

Triangular Matrices

Triangular matrices are fundamental in decompositions, such as LU Decomposition. They come in two main varieties: lower triangular and upper triangular matrices.

• Lower Triangular Matrix: A matrix where all the entries above the main diagonal are zero.
• Upper Triangular Matrix: A matrix where all the entries below the main diagonal are zero.

A key feature of triangular matrices is that performing computations, like determining the determinant or solving linear systems, is significantly more straightforward compared to general matrices. In the LU decomposition, a matrix \( A \) is expressed as the product of a lower triangular matrix \( L \) and an upper triangular matrix \( U \), \( A = LU \).
These triangular forms simplify many algebraic computations and are crucial for understanding the behavior and solutions related to matrix \( A \) in the context of LU decomposition. However, as seen in the problem, the antisymmetric nature of matrix \( A \) complicates this standard approach and requires pivoting for a successful decomposition.