# Does the equation QX=B have solutions?

Given Q $\in \mathbb{R}^{n\times n}$ Orthogonal matrix and X,B $\in \mathbb{R}^{n\times n}$ generic matrixes. Demonstrate that the equation QX = B has solutions and provide an algorithm which provides the solution in not more than 2$n^3$ ops.

My solution: First thing which i thought could help me was that i know QX=B has a solution since Q is orthogonal and we know that given AX=b the equation has a solution if A is invertibile(Using Gauss Elimination) so having Q orthogonal it is also invertible therefore the original equation does have solution.

Now regarding the solution itself i know from a theorem in QR factorization that "Given A,Q,R $\in \mathbb{R}^{n\times n}$ where R is upper triangular and Q orthogonal, A = QR "

I'm certain i would need to apply QR factorization here.

Where I'm stuck:

1. I don't know how i could apply the QR facotrization theorem here, since I'm dealing with the reverse problem of the one in the theorem.

2. How could I apply the QR facotrization here step by step? in normal cases i would apply it to a single matrix and then find the solutions to vector column of X here i have X as a matrix.

Thank you!

-

I think you're just missing the definition of orthogonal matrix, which tells us that $Q^T Q = I$. So $X = Q^T B$ using ordinary matrix multiplication seems to solve the problem.
That is, the solution $X = Q^T B$ exists and can be calculated in $2n^3$ operations by multiplying the transpose of $Q$ times $B$. There are $n^2$ entries of $X$ to be computed, so it suffices to explain how any one of them can be found with less than $2n$ operations.
The $ij^{th}$ entry of $X$ is the "dot product" of the $i^{th}$ column of $Q$ and the $j^{th}$ column of $B$ (note the $i^{th}$ column of $Q$ becomes the $i^{th}$ row of $Q^T$, the transpose of $Q$). This "dot product" involves the $n$ multiplications of corresponding entries together with $n-1$ additions of those products, for a total of less than $2n$ floating point operations for each entry of $X$.
The "schoolbook" algorithm for matrix multiplication of $Q^T B$ requires no more than $2n^3$ floating point operations (multiplications and additions, up to a few lower-order terms) regardless of how "dense" $B$ (or $Q$) happen to be. So I don't think you need $B$ to be upper triangular, if "solving" means to produce $X$. Of course some work has to be done if you insist on finding a QR factorization of $X$ as well. –  hardmath Feb 14 '13 at 15:47
Well i'm asked to find if the equation has solution and then provide an algorithm which calculates X in not more than 2$n^3$. The second part is actually confusing me. I mean i have never solved an equation with Xs comprised of a matrix. I usually think they are given in a Column Matrix form but then again i suck at maths. –  tutak Feb 14 '13 at 16:12
I've spelled out the computation of $X$, which is another way to show the solution exists, and explained why the operations are not more than $2n^3$ in solving for $X$. –  hardmath Feb 14 '13 at 16:22