QR factorization: $A=QR$ and $R=Q^TA$ gives $Q Q^T = I$

Question

I am learning linear algebra and I am on QR factorization: $A = QR$. A solution to $R$ is $R = Q^TA$, where $Q$ and $A$ have size $m * n$ and $R$ is $n * n$, which means that $Q$ is not necessarily square.

My question:

Since $A = QR$, if we substitute the R in $A = QR$ with $Q^TA$ then we get $A = QQ^TA$, which means $QQ^T = I$. However, $QQ^T$ shouldn't be equal to $I$ unless $Q$ is square. So there must be something wrong with my deduction above. What went wrong?

Update: I emailed professor Strang at MIT and found the answer

Answer 1

I have chosen to delete my original answer and write a new one. I do this since neither my first answer nor the answer the OP has provided address the differences between the full and reduced $QR$ factorizations, which have come into play here and probably caused some misunderstandings. I first the briefly describe the difference, before I address what the question is really about, namely the product $QQ^\top$

The reduced $QR$ decomposition. A reduced $QR$ decomposition is a composition of $A$ into a product $A= QR$, where $Q$ is an $m \times n$ matrix with orthonormal columns and $R$ an $n \times n$ upper triangular matrix. Note that $A$ needs to be either square ($m=n$) or tall ($m > n$) since the columns of $Q$ need to be linearly independent. The columns of $Q$ form an orthonormal basis of the columns space of $A$.

The full $QR$ decomposition. The full $QR$ decomposition is obtained by extending the orthonormal basis for the column space of $A$ to an orthonormal basis of the entire space. In this case $R$ will be an upper triangular $m \times n$.

Now, in both cases $Q^\top Q = I$ since the columns of $Q$ are orthonormal. However in the first case, the opposite product is not the identity. As Strang points out in his lecture notes, $QQ^\top$ will be the projection onto the column space of $Q$ (or equivalently $A$), which when $Q$ does not span the entire space, will not be $I$. In the case of the full decomposition however, $Q$ is square and spans the whole space, so we have $Q^\top Q = Q Q^\top = I$. Please note that there is a typo in Strang's notes, as the projection matrix should be

$$P = Q (Q^\top Q)^{-1} Q^\top.$$

The OP is right that you get that $A = QQ^\top A$ in any case. However, you can not "cancel out" matrices in the same way as with numbers. You need to multiply both sides by the inverse, which does not exist if $Q$ is not square. The reason why $QQ^\top A = A$ in any case, is that, as the OP has pointed out in his answer, $QQ^\top$ projects into the column space of $A$, and the columns of $A$ will therefore be eigenvectors of $QQ^\top$.

Answer 2

In QR Decompositon $A$ is $m*n$ matrix, $Q$ is $m*m$ orthogonal matrix, $R$ is $m*n$ upper triangular matrix. Orthogonal matrix are always square matrix.

Answer 3

will be identity but may not be $n\times n$ could be $m\times m$ as well. $Q$ is $m\times n$, $R$ is $n\times n$, $A$ is $m\times n$ and $Q^T$ is $n\times m$. so $Q^TQ$ and $QQ^T$ is well defined and makes complete sense.

Answer 4

Answering my own question here:

I emailed Professor Gilbert Strang at MIT asking about this and he helped me find the answer:

$QQ^T$ is indeed not $I$, actually it is the projection matrix that given a vector $v$, $QQ^T * v$ projects $v$ onto the column space of Q, which is the column space of A (See "Orthonormal columns are good" section in the lecture notes for more details). So $QQ^TA$ is essentially projecting every vector in A to the column space of A and the projection of each vector is the vector itself.