Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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$.

share|improve this answer
    
It does indeed make it pretty simple and something I hadn't thought about. However B is still not Upper Triangular, how do you think should my algorithm work? Just make B triangular independently of Q? –  tutak Feb 14 '13 at 15:41
    
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
    
Thank you very much :) –  tutak Feb 14 '13 at 16:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.