QR Decomposition

Let be a matrix such that and , then there exists an orthogonal matrix and an upper triangular matrix such that .

With this decomposition we can solve equations easily using the properties of orthogonal matrices:

To find and we first express as follows:

Now since we know that . We can now apply the Gram-Schmidt Method with normalization to get an Orthonormal Basis that spans which we will call . Next we project onto our new basis by doing the following:

We can then write the system of equations in a compact way:

This gives us the thin QR Decomposition of , in particular, is the thin QR Decomposition of when:

To get the Full QR Decomposition of we need to have orthonormal columns, in the thin decomposition we only had to get those extra columns we use the orthonormal basis of to do this we may want to use properties of Fundamental Subspaces to realize that , once we find this we can use the Gram-Schmidt Method again with normalization to get which we can then combine into a matrix . Finally we get that: