4
$\begingroup$

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

  • 0
    Most likely the answer depends on the norms you use.2011-11-02
  • 1
    The matrix you are looking for simply does not exist. For any $m$-by-$n$ matrix $A$ (with $m$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. – 2011-11-02
  • 0
    @user1551: You are right. Thank you for the answer.2011-11-03

2 Answers 2

3

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.

  • 0
    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?2011-11-02
  • 0
    Is the contradiction clearer? What does the "faux orthogonality" refer to?2011-11-02
  • 0
    @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)?2011-11-02
  • 0
    @Srivatsan: $A$ is not a square matrix. It seems that the proof assumes that $A$ is square. Am I mistaken?2011-11-02
  • 0
    @Srivatsan: I think it can be left as it is. Thanks for the attempt though.2011-11-02
  • 0
    "faux orthogonality" is what I spontaneously made up to refer to a scalar multiple of an orthogonal matrix. :) Anyway, how is $\|Az\|<\|Ay\|$ and $\|z\|>\|y\|$ an immediate contradiction? You have to use the fact $A$ is a scalar multiple of an orthogonal matrix in order to derive the contradiction, and if you're utilizing the orthogonality either way it makes introducing $z$ and $\beta$ sorta superfluous I think...2011-11-02
  • 0
    @jpv Can you give us an example of such a rectangular matrix you might have encountered? That might help. =)2011-11-02
  • 0
    @Srivatsan: Any matrix with condition number equal to one is a matrix of this type. I have been trying to obtain an "if and only if" condition that all such matrices have to satifsy but did not have any luck.2011-11-02
  • 0
    @jpv Thanks. I will update the answer if the answer is salvageable at all.2011-11-02
0

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.

  • 0
    This assumes you have $m>n$, the opposite of what your question says. As @user1551 points out, with $m2011-11-02