0
$\begingroup$

This is my first time asking a question here. Thus, I apologise in advance if it is not articulated correctly or something else turns out to be wrong with it. Before asking the question itself, consider the following $2 \times 2$ correlation matrix:

$$\begin{pmatrix}1 & \rho\\\ \rho & 1\end{pmatrix}$$

The condition number of a symmetric matrix is an absolute value of ratio between its greatest and lowest eigenvalues, which, in this case, increases with the absolute value of $\rho$,

$$\kappa = \frac{1+|\rho|}{1-|\rho|}$$

I want to show that as dimension of a matrix increases, the condition number generally tends to increase too. However, how to formally even write the proposition? I can consider some constant $\hat{\rho}$ and say that for larger matrices all entries satisfy $|\rho| > \hat{\rho}$, or maybe another constraint that all non-diagonal entries have to be equal (basically, if we have some $\tilde{\rho}$ for 2x2 case, then all non-diagonal entries for larger matrices are equal to $\tilde{\rho}$) but still no idea how to prove even that.

If you find this task interesting, or at least have ideas where to start, I would love to hear your suggestions!

$\endgroup$
1
  • $\begingroup$ I think the answer heavily depends on what you mean by "generally". $\endgroup$ Commented Jun 26, 2023 at 13:42

2 Answers 2

Reset to default
1
$\begingroup$

I want to show that as dimension of a matrix increases, the condition number generally tends to increase too.

There's not really a way to formalize this because it's not really true. My answer will have two parts:

  1. Using diagonal matrices, I show that your desired statement is not really true.
  2. I show why there is some formalization that might help if you think about "growing dimension" more precisely as nested principal minors.

Diagonal Matrices

It's possible to construct sequences of matrices where the dimension grows and the behavior of the condition number can be arbitrary: it can increase, decrease, or remain constant. The simplest case to study this is diagonal matrices with positive entries, i.e. $$ D = \begin{bmatrix} d_1 & & \\ & \ddots & \\ & & d_n \end{bmatrix} \enspace, $$ where $d_1, \dots d_n > 0$. Recall that the eigenvalues of $D$ are its diagonal entries $d_1, \dots d_n$ and that for symmetric matrices, the condition number is the ratio of the largest and smallest eigenvalues. In other words, the condition number of $D$ is $\kappa(D) = d_{\max} / d_{\min} \geq 1$. The condition number of the diagonal matrix doesn't depend on its dimension (which is $n$) but rather the ratio of its largest and smallest eigenvalues. Only by changing $d_1 \dots d_n$ (and not really the dimension $n$) do we change the condition number. This example shows how it's possible to construct sequences of matrices where the dimension grows and the behavior of the condition number can be arbitrary (I'm happy to elaborate on this if it's not clear).

Nested Principal Minors

On the other hand, there is some sense in which your statement can be made formal when you replace "increasing dimension" with "nested principle minors". The simplest example of a principle minor is the $k$-by-$k$ submatrix that corresponds to taking the first $1 \dots k$ rows and columns. But let me add that I would not interpret this next statement as generally meaning that "condition number increases with dimension". The proof uses Cauchy Interlacing Theorem.

Theorem: Let $A$ be an $n$-by-$n$ symmetric positive definite matrix. Let $A_1 \dots A_n$ be a sequence of nested principal minors of $A$. Then, the condition number satisfies the inequalities $\kappa(A_1) \leq \cdots \leq \kappa(A_n)$.

Proof: Let $A'$ be an $m$-by-$m$ principal minor of $A$, where $m \leq n$. Without loss of generality, it suffices to show that $\kappa(A') \leq \kappa(A)$. Let $0 < \lambda_1 \leq \dots \leq \lambda_n$ be eigenvalues of $A$ and let $0 < \lambda'_1 \leq \dots \leq \lambda'_m$ be the eigenvalues of $A'$. By Cauchy Interlacing theorem, $\lambda_1 \leq \lambda_1'$ and $\lambda'_m \leq \lambda_n$. Thus, the condition number satisfies the inequality $$ \kappa(A') = \frac{\lambda_m'}{\lambda_1'} \leq \frac{\lambda_n}{\lambda_1} = \kappa(A) \enspace. \blacksquare $$

$\endgroup$
2
  • $\begingroup$ Thank you so much! This actually helped. $\endgroup$ Commented Jun 27, 2023 at 11:23
  • $\begingroup$ Great - glad it helped :) $\endgroup$ Commented Jun 27, 2023 at 13:01
0
$\begingroup$

It is an Idea (I'm no probabilist) but you could define a probability measure on matrix verifying $\|A\| < 1$ (subordinate norm) (since it has finite measure you could choose the uniform probability) And find some properties about $$\mathbb{E}(\text{Condnum}(X))$$ or $$\mathbb{V}(\text{Condnum}(X))$$ with respect to the dimension. If one of these explodes it seems like it translates what you wanted to express?

$\endgroup$
3
  • $\begingroup$ The answer will be very dependent on the distribution that you choose. In other words, you can choose distributions on matrices so that the condition number increases, decreases, or remains constant with $d$. $\endgroup$ Commented Jun 27, 2023 at 1:51
  • $\begingroup$ For certain classes of random matrices (i.i.d. subgaussian rows, for example) the singular values concentrate with high probability and so the condition number will stay close to 1 as the dimension grows. $\endgroup$ Commented Jun 27, 2023 at 1:54
  • $\begingroup$ For example, with standard normal entries, the condition number grows like $\log n$ math.mit.edu/~edelman/homepage/papers/Eig.pdf $\endgroup$ Commented Jun 27, 2023 at 1:54

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.