Question

(a) Let \(Q\) be an orthogonal \(m \times m\) matrix and \(R\) an \(n \times n\) upper triangular matrix, \(m>n\), such that $$ A=Q\left(\begin{array}{l} R \\ 0 \end{array}\right) $$ Show that the diagonal elements of \(R\) all satisfy \(r_{i i} \neq 0, i=1, \ldots, n\), if and only if \(A\) has full column rank. (b) Next, let \(Q\) be \(m \times n\) with orthonormal columns (so \(Q^{T} Q=I\), but \(Q\) does not have an inverse) such that $$ A=Q R $$ Prove the same claim as in part (a) for this economy size decomposition.

Short answer

Question: Prove that for a matrix A with QR decomposition, the diagonal elements of R are non-zero if and only if A has full column rank. Solution: We have analyzed two cases: (a) A is an m x m matrix, and (b) A is an m x n matrix. In both cases, we have shown that if the diagonal elements of R are non-zero, then A has full column rank, and conversely, if A has full column rank, the diagonal elements of R are non-zero. This proves the statement.

Step-by-step solution

(a) Proving the diagonal elements are non-zero for m x m case

Consider the given QR decomposition of A: \(A=Q\left(\begin{array}{l} R \\\ 0 \end{array}\right)\), where Q is an orthogonal m x m matrix, and R is an n x n upper triangular matrix. First, let us consider the given condition that the diagonal elements of R are non-zero. In other words, \(r_{ii} \neq 0\) for \(i=1, \ldots, n\). To show that A has full column rank, we need to show that columns of A are linearly independent. Since Q has orthonormal columns, we can write \(A\) as: $$ A = Q \left(\begin{array}{cccc} r_{11} & r_{12} & \cdots & r_{1n} \\ 0 & r_{22} & \cdots & r_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & r_{nn} \\ 0 & 0 & \cdots & 0 \end{array}\right) $$ Multiplying Q with the matrix above, the columns of A can be expressed as linear combinations of the columns of Q. Since Q has orthonormal columns (therefore, the columns of Q are linearly independent), and the diagonal elements of R are non-zero, it follows that the columns of A are also linearly independent. Therefore, A has full column rank. Now, we will prove the converse. Suppose A has full column rank, which means its columns are linearly independent. We will show that the diagonal elements of R are non-zero. Since A has full column rank, and Q has orthonormal columns (hence, Q has full column rank), the matrix R must have non-zero diagonal elements. If any diagonal element of R is zero, then the corresponding column in A will be a linear combination of the previous columns, which contradicts that A has full column rank. Therefore, the diagonal elements of R are non-zero.

(b) Proving the diagonal elements are non-zero for m x n case

For this case, A is given as an m x n matrix, and its QR decomposition is given as \(A = QR\), where Q is an m x n matrix with orthonormal columns, and R is an n x n upper triangular matrix. Similar to the proof in case (a), we first consider the given condition that the diagonal elements of R are non-zero (\(r_{ii} \neq 0\) for \(i=1, \ldots, n\)). Since Q has orthonormal columns (which are linearly independent), and the diagonal elements of R are non-zero, it follows that the columns of A are also linearly independent (the proof is identical to that of (a)). Therefore, A has full column rank. Now, let's prove the converse. Suppose A has full column rank, which means its columns are linearly independent. We will show that the diagonal elements of R are non-zero. Since A has full column rank, and Q has orthonormal columns (hence, Q has full column rank), the matrix R must have non-zero diagonal elements. The proof is identical to that of (a), showing that if any diagonal element of R is zero, then the corresponding column in A will be a linear combination of the previous columns, which contradicts that A has full column rank. Therefore, the diagonal elements of R are non-zero. In both cases (a) and (b), we have shown that the diagonal elements of R are non-zero if and only if A has full column rank.

Key concepts

Orthogonal Matrix

Understanding the concept of an orthogonal matrix is key to delving into more complex algebra topics, especially within the realm of QR decomposition.

An orthogonal matrix is a square matrix Q with the fascinating property that its transpose is also its inverse, mathematically expressed as \( Q^TQ = QQ^T = I \), where \( I \) stands for the identity matrix. This relationship implies that the matrix has orthonormal columns, meaning that each column vector has a magnitude of 1 and is orthogonal (at a right angle) to all other column vectors in the matrix. Orthonormality is essential because it ensures that the columns are linearly independent.

When such an orthogonal matrix is used in QR decomposition, it preserves the length and orthogonality of vectors after transformation, which is crucial for maintaining the linear independence of the columns of the resulting matrix A, as seen in the given exercise.

Upper Triangular Matrix

The next concept crucial for understanding QR decomposition is the upper triangular matrix. This type of matrix, represented in the solution as \( R \), is essentially a square matrix where all the entries below the main diagonal are zero.

Properties of Upper Triangular Matrices

One of the important properties of such matrices is that the determinant is the product of the diagonal entries, making it simple to verify whether the matrix is invertible (a non-zero determinant indicates that it is invertible).

In the context of QR decomposition, an upper triangular matrix plays a pivotal role. If the matrix R has non-zero elements on its diagonal as stated in the exercise, it ensures the invertibility of R and consequently the full column rank of matrix A when it is multiplied by an orthogonal matrix Q. This is directly linked to the concept of linear independence and the ability to solve linear equations efficiently.

Full Column Rank

Finally, the concept of 'full column rank' is critical to fully appreciate the implications of QR decomposition. A matrix has full column rank if all of its columns are linearly independent; in simpler terms, no column can be written as a combination of the others.

This attribute is highly significant in many applications, including solving systems of linear equations and statistics.

Linking Full Column Rank and QR Decomposition

In the exercise, we explored how the non-zero diagonal elements of R in QR decomposition directly imply that the matrix A has full column rank. This is because linear independence in the columns of Q (thanks to orthonormality) paired with non-zero diagonal elements of R ensures that none of the columns of A are redundant or expressible as a combination of its other columns.

Achieving full column rank is desirable as it indicates that the dataset is rich and that the matrix forming from it can be useful for unique solutions in linear algebra problems.