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.

Let $A$ be an $m\times n$ matrix such that $m < n$. I would like to know the conditions on $A$ such that the following is true:

$$\|Ax\| \leq \|Ay\| \implies \|x\| \leq \|y\|$$

It can easily be shown that if $\kappa(A)=1$ (condition number) then this property is satisfied. I am looking for the most general type of matrices that satisfy this condition.

Any help is much appreciated.

Thanks, Phanindra

share|improve this question
    
Most likely the answer depends on the norms you use. –  Dirk Nov 2 '11 at 7:14
1  
The matrix you are looking for simply does not exist. For any $m$-by-$n$ matrix $A$ (with $m<n$), let $x$ be a nontrivial solution of $Ax=0$ and let $y=0$. Then $\|Ax\|=\|Ay\|=0$ but $\|x\|>\|y\|=0$, regardless of what norm is used. –  user1551 Nov 2 '11 at 9:28
    
@user1551: You are right. Thank you for the answer. –  jpv Nov 3 '11 at 2:25
add comment

2 Answers

EDIT: This answer mistakenly assumes that $A$ is a square $n \times n$ matrix.

I assume we're working over $\mathbb R$. We claim that $A$ must be a scalar multiple of an orthogonal matrix.

First, we prove that if $\| x \| = \| y \|$, then $\| A x \| = \| A y \|$. Towards a contradiction, assume that $\| x \| = \|y \|$ and $\| A x \| \neq \| A y \|$. Without loss of generality, we can assume that $\| Ax \| < \|A y \|$. Moreover, it is clear that both $x$ and $y$ are nonzero. (Why?) Now, fix a number $\beta$ such that $$ 1 < \beta < \frac{\| A y \|}{\| Ax \|}. $$ Then, defining $z = \beta x$, it is clear that

  • $\| A z \| = \beta \| A x \| < \| A y \|$.

  • $\| z \| = \beta \| x \| = \beta \| y \| > \| y \|$.

This is a contradiction to the hypothesis (since $\| A z \| < \| A y \|$ but $\| z \| > \| y \|$). Hence, if $\| x \| = \| y \|$, then $\| A x \| = \| A y \|$.

It now remains to show that $A$ is a multiple of an orthogonal matrix. Fix a unit vector $u$. Then since $\| x \| = \| (\| x \| u) \|$, it follows from (2.) that $\| A x \| = \| A (\| x \| u) \| = \| x \| \cdot \| A u \|$. Now, if $\| A u \| = 0$, then $A$ must be the zero matrix (why?) and we are already done. On the other hand, assuming $\| A u \| > 0$, it is easy to see that the matrix $$ B := \frac{1}{\| A u \|} A $$ is a linear isometry and hence orthogonal.

share|improve this answer
    
I don't understand how the two bullet points are a contradiction to a hypothesis. Anyway, why introduce $z$ and $\beta$ instead of just using $A$'s faux orthogonality by writing $\|Ax\|=\|\lambda U x\| = |\lambda| \|x\|$ and similarly for $y$, deriving a contradiction? –  anon Nov 2 '11 at 4:15
    
Is the contradiction clearer? What does the "faux orthogonality" refer to? –  Srivatsan Nov 2 '11 at 4:18
    
@jpv Uh oh, didn't see that $A$ is rectangular =). Do you want me to remove the answer or can I leave it as it is (assuming I cannot fix the answer)? –  Srivatsan Nov 2 '11 at 4:20
    
@Srivatsan: $A$ is not a square matrix. It seems that the proof assumes that $A$ is square. Am I mistaken? –  jpv Nov 2 '11 at 4:20
    
@Srivatsan: I think it can be left as it is. Thanks for the attempt though. –  jpv Nov 2 '11 at 4:22
show 4 more comments

You just want the SVD. There exist unitary matrices U and V and a diagonal matrix Σ with non-negative real entries such that:$$A=U\Sigma V^* \qquad \|Ax\| = \|U\Sigma V^*x\| = \|\Sigma V^*x\|$$ So take x amongst the columns of V to get that all entries of Σ have equal value, so that A is more or less a scalar multiple of a unitary matrix, just possibly rank deficient since it is not square: $$A = \lambda UV^*$$

Here you can require λ to be non-negative, but this is just absorbing complex scalars of absolute value 1 into the unitary matrices.

share|improve this answer
    
This assumes you have $m>n$, the opposite of what your question says. As @user1551 points out, with $m<n$, Σ has to have some diagonal entries being 0. –  Jack Schmidt Nov 2 '11 at 15:49
add comment

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.