Question

Let \(A\) be positive definite and write \(d_{r}=\operatorname{det}^{(r)} A\) for each \(r=1,2, \ldots, n .\) If \(U\) is the upper triangular matrix obtained in step 1 of the algorithm, show that the diagonal elements \(u_{11}, u_{22}, \ldots, u_{n n}\) of \(U\) are given by \(u_{11}=d_{1}, u_{j j}=d_{j} / d_{j-1}\) if \(j>1\). [Hint: If \(L A=U\) where \(L\) is lower triangular with \(1 \mathrm{~s}\) on the diagonal, use block multiplication to show that \(\operatorname{det}^{(r)} A=\operatorname{det}^{(r)} U\) for each \(\left.r .\right]\)

Short answer

The diagonal elements of the upper triangular matrix \(U\) are related to successive determinants of the leading principal minors of \(A\) as \(u_{11}=d_1\) and \(u_{jj}=d_j/d_{j-1}\) for \(j>1\).

Step-by-step solution

Understanding the Setup

We are given a positive definite matrix \(A\) and its LU decomposition, where \(L\) is a lower triangular matrix, and \(U\) is an upper triangular matrix. The exercise asks us to relate the elements of \(U\) to the determinants of leading principal minors of \(A\).

Setting Up the LU Decomposition

We consider the LU decomposition \(LA=U\), where \(L\) is a lower triangular matrix with ones on the diagonal and \(U\) is an upper triangular matrix. By properties of determinants, \(\det(A) = \det(L)\cdot\det(U)\). Because \(L\) has ones on its diagonal, \(\det(L) = 1\). Thus, \(\det(A) = \det(U)\).

Understanding Block Multiplication

To relate \( \det^{(r)} A = \det^{(r)} U \) for each \(r\), consider block triangular matrices. A key property is that the determinant of a triangular matrix is the product of its diagonal entries. Hence, for block triangular matrices, the determinant of the blocks are related to projections of the triangular matrices.

Expressing Diagonal Elements of U

Given that \(u_{11} = d_1\) and for \(j > 1\), \(u_{jj} = \frac{d_j}{d_{j-1}}\), we need to justify these formulas by expanding the matrices or considering submatrices, each corresponding to the \(j\)-th leading principal submatrix.

Prove \( \operatorname{det}^{(r)} A = \operatorname{det}^{(r)} U \)

Using the block multiplication approach and the property of determinants for triangular matrices, we find that the determinant relationship for a submatrix of \(A\) and \(U\) holds due to their structure (since \(L\) has 1's in the diagonal and doesn't change the determinant between \(A\) and \(U\)).

Applying Formulas to Diagonal Elements

With \(d_1 = u_{11}\), and \( u_{jj} = \frac{d_j}{d_{j-1}} \) for \(j>1\), infer that these formulas come from simplifying each step of expanding the determinants based on previous steps, and verifying each step with determinants, substantiating the above determinant equality and the stepwise triangular forms.

Key concepts

Positive Definite Matrix

A positive definite matrix is a key concept in linear algebra. This type of matrix is always square and symmetric. Positive definiteness signifies that for any non-zero vector \(x\), the product \(x^T A x\) produces a positive value. This property ensures stability and common applications in optimization problems and physics.
The following are important characteristics of positive definite matrices:

• All eigenvalues are positive.
• For a Hermitian matrix \(A\), \(x^* A x > 0\) for any non-zero complex vector \(x\).
• Each principal minor of the matrix is positive.

Recognizing these attributes helps when working with matrices in LU decomposition to confirm the matrix behavior stays predictable.

Block Multiplication

Block multiplication is a method used to simplify operations on large matrices. Consider a matrix that can be partitioned into smaller sub-matrices, called blocks. By focusing on these blocks, matrix multiplication can be handled more efficiently.
Block multiplication is especially handy in LU decomposition:

• It divides the matrix into simpler parts.
• Calculations are easier with smaller dimensions.
• The properties of block triangular and block diagonal matrices simplify determinant calculations.

In essence, block multiplication captures the structure of matrices and makes it feasible to leverage smaller blocks to solve problems related to triangular matrices or positive definite matrices efficiently.

Principal Minors

Principal minors are determinants of square submatrices formed by deleting certain rows and columns from the original matrix. They are an essential aspect when determining if a matrix is positive definite.
For a matrix \(A\):

• Each leading principal minor is formed from the top-left corner of the matrix.
• They indicate the matrix's behavior and rank.
• In LU decomposition, principal minors help understand the determinant relations within the lower and upper triangular matrices.

Thus, analyzing principal minors gives insights into matrix properties and assists in proving relationships between different decompositions.

Triangular Matrix

A triangular matrix is a special form of a square matrix, either lower or upper triangular. In the context of LU decomposition, triangular matrices are crucial.
Here's why they matter:

• Upper triangular matrices have non-zero entries only at or above the diagonal.
• Lower triangular matrices have non-zero entries only at or below the diagonal.
• The determinant of a triangular matrix is simply the product of its diagonal entries.

These properties make them highly efficient for calculations, especially within algorithms for solving systems of linear equations and for simplifying matrix expressions when combined with block matrix techniques.