# Upper bound on condition number of row-normalized matrices

I would like to study the condition number of a non-square normalized matrices as function of the original non row-normalized matrix.

Let $$X \in \mathbb{R}^{a \times b}$$ (for $$a > b$$). We obtain $$\hat X$$ by taking all the rows of $$X$$ and normalizing them such that the $$\ell_2$$ norms of each row is $$1$$. We can further assume that all the rows of $$X$$ are $$1 \leq \|x_i| \leq \alpha$$

### Question

I believe (and I would like to prove) that: $$\kappa(\hat X) \leq \kappa(X).$$

For me, the condition number of a matrix $$X$$ is defined as the ratio between the biggest and the smallest singular value of $$X$$, i.e.:

$$\kappa(X) = \frac{\sigma_1}{\sigma_k}$$

where $$k$$ is the rank of the matrix (which can be smaller than $$b$$)

I think a property of matrix norm might come handy: its submultiplicativity: $$\|AB\| \leq \|A\|\|B\|$$ from which it possible to derive the property that $$\kappa(AB) \leq \kappa(A)\kappa(B)$$ (this is true only in some casis, see referenced questions at the bottom)

We recall that the norm of a matrix can be defined from a ($$\ell_p$$ which in our case is $$\ell_2$$)

$$\| A \| = \max_{x \neq 0, } \frac{\|Ax\|}{\|x\|} = \max_{\|x\|=1} \|Ax\| = \sigma_1$$

# My attempt:

In general, it is easy to see that $$\sigma_1(\hat X) < \sigma_1(X)$$, while I cannot prove that $$\sigma_{min}(\hat X) > \sigma_{min}(S)$$ for the smallest singular values.

This is how I approached the proof: Let me recall you that the condition number, which usually for square matrices is defined as $$\kappa(X) = \|X\| \|X^{-1}\|$$ for the case of non-square matrices can be better defined as the ratio between the biggest and the smallest singular value. In other words: $$\kappa(X)= \|X\|\|X^+\|$$ (where $$X^+$$ is the Moore-Penrose pseudoinverse of $$X$$, i.e. the matrix obtained by taking the inverse $$1/\sigma_i$$ of the singular values of $$\sigma_i$$ of $$X$$ ).

We can think of $$X$$ as the product of $$\hat X$$ where I left multiply by $$N_X \in \mathbb{R}^{n \times n}$$ , a diagonal matrix where the entry in position $$ii$$ is just $$\|x_i\|$$, i.e. the norm of row $$i$$. $$X = N_X \hat X.$$

I thought that I can express the condition number as product of the norm. Unfortunately, this direction seems to lead me astray, as the inequality is in the wrong direction.

So: $$\kappa(X) = \|N_X\hat X\| \|(N_X \hat X)^{+}\|=\|N_X\hat X\| \|\hat X^{+}N_X^{+} \| \leq \|N_X\| \|\hat X\| \|\hat X^{+}\|\|N_X^{+} \|$$

and also $$\kappa(\hat X) = \|\hat X\| \|\hat X^{-1}\|$$.

Also note that $$\kappa(N_X) = \kappa(N_X^{-1}) \leq \alpha$$, because of our assumption on the value of the norms of the rows of $$X$$.

This is equivalent of asking if these two conditions are satisfied:

• $$\|\hat X\| \|\hat X^{+}\| \leq \|N_X\hat X\| \|(N_X \hat X)^{+}\|$$
• $$\| \hat X^+ \| \leq \|(N\hat X)^+ \|$$

It is simple to observe that: $$\|\hat X\| \leq \|N\hat X\|$$. This is because, by using the definition of norm of a matrix, $$\forall y \text{ s.t. } \|y\|=1 \text{ we have that } \|\hat Xy\| \leq \|N \hat Xy\|$$ because each element on the diagonal is bigger than 1. We need to see if $$\|\hat X^{+}\| \leq \|(N\hat X)^+\| = \|(\hat X^{+}N^{+})\|$$

I am looking here for some monotonicty properties of matrix norms, or property that can be derived from the inverse of a matrix. Am I going in the right direction? Thanks.

What if we start from $$N^{-1}_XX = \hat X$$? Then, I would obtain $$\kappa(\hat X) = \kappa(N^{-1}_X X) \leq \kappa(N^{-1}_X)\kappa(X) \leq \alpha \kappa(X)$$ This does not seems helpful, because we get to the point where $$\kappa(\hat X) \leq \alpha \kappa(X)$$ and, from the previous observation, $$\kappa(X) \leq \alpha \kappa(\hat X)$$

## Experiments

I checked that this property is satisfied in two cases:

• if we have a diagonal matrix $$X$$ with some random scalar in it, then the normalized version is just the identity matrix, whose condition number is 1.

• for random matrices (random in sense of numpy.random.rand() ) it holds true that $$\kappa(\hat X) \leq \kappa(X)$$

## Related questions

There are numerous questions around the condition number of product of matrices:

In the last question they show a counterexample for $$\kappa(AB)\leq\kappa(A)\kappa(B)$$ which apparently does not hold for non-square matrices.

• A bit long. Please consider breaking into sections. Jun 6, 2020 at 10:22
• You start from $X = N_X \hat X$ leading to an inequality in the wrong direction. So then just start from $N_X^{-1} X = \hat X$ to get an inequality in the other direction. Does that help? Jun 7, 2020 at 13:30
• actually it does not seems helpful.. i edited the question to include the comment. probably there something i don't understand from this. Jun 9, 2020 at 11:32

Being not able to prove it I found $$\begin{pmatrix} -1 & 0\\ -1 & 1\\ 1 & 0 \end{pmatrix}$$ and $$\begin{pmatrix} 4 & -2 & 3\\ -3 & -3 & -3\\ 3 & -2 & 4 \end{pmatrix}$$ if you are interested in square matrices.