When diagonalizing a matrix, do the square matrices multiplied with the original matrix have to be invertible?

Question

Let's say we're converting a matrix $A$ into a diagonal matrix by the well-known algorithm: exchange rows and columns until the smallest element is placed on the $a_{11}$ position, and all other elements in this row and column are $0$. These actions are accomplished by multiplying with elementary matrices-exchanging rows, for example, is facilitated by multiplying $A$ with $\begin {pmatrix} 1&0&0&0\\0&0&1&0\\0&1&0&0\\0&0&0&1\end{pmatrix}$ if $A$ is a $4\times4$ matrix and we're exchanging the second and third rows. After this step is completed, we focus on the $3\times3$ matrix left, and again bring the lowest element to the $a_{22}$ position. This is facilitated by multiplying with the matrix $\begin {pmatrix} 0&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0\end {pmatrix}$, if we wish to exchange the second and third rows of the remainder $3\times3$ matrix. This matrix is not invertible, and neither is its product with the former invertible elementary matrix.

Hence, I don't understand how, when we say a matrix is diagonalized, we say $A'$ (the diagonalized matrix) $=QAP^{-1}$, when P may not even be invertible.

Answer 1

The second matrix should simply contain a 1 in the 1-1 position. There is no reason to zero out that row of that permutation matrix. (In fact, one shouldn't really call it a permutation matrix if you make it singular like that.)

The presence of that 1 simply repeats the top row of the matrix you are multiplying it with, and so it won't be changed.

In general, there will be a growing identity matrix in the upper left hand corner of your permutation matrix, reflecting the fact that you want to leave those rows which you have already worked on unchanged. Something similar can be said for the column operations that you do on the right: the growing identity matrix reflects that you have stopped altering the first several columns.