5
$\begingroup$

I have two questions, the second of which is related to this question posed by Denis Serre.

Let $X$ be a random variable and suppose that $Y=|X|$ (e.g., $Y$ could be the folded normal distribution). If $M$ is an $n$-by-$n$ random matrix with iid entries from $Y$, then:

  1. Is the method above an appropriate way to generate a random nonnegative matrix?
  2. If the answer to the first question is 'yes', what is the expected value of the spectral radius of $M$? If this is not available, is there an asymptotic description of the spectral radius as $n \longrightarrow \infty$?

Thanks in advance for your kind assistance.

$\endgroup$
2
  • $\begingroup$ @AnthonyQuas That can't be right, the spectral radius is at least the minimum row sum. $\endgroup$ Jun 16, 2017 at 23:25
  • $\begingroup$ Oops. Yes. I agree. And of course what you're saying is the right asymptotic. $\endgroup$ Jun 17, 2017 at 0:11

4 Answers 4

5
$\begingroup$

To amplify on Brendan's answer:

You are dealing with a matrix of zero mean iid's plus a rank one perturbation: $M=W+ A$ where $A=c11^T$ and $c=EY$. The spectral norm of $W$ is asymptotically $2\sqrt{n} \sigma$ where $\sigma^2=\mbox{ Var}(Y)$, see Geman's 1980 paper (at least when $Y$ has good moment growth). However, the rank one perturbation has norm $cn$, as can be seen by multiplication with the vector $n^{-1/2} (1,\ldots,1)$. So the norm of $M$ is about $cn$ with error at most $2\sqrt{n}\sigma$, with high probability.

If $Y$ has heavy tail, everything changes - the norm may be dominated by the maximal entry of $M$. This is the case if the entries are for example $\alpha$-stable with $\alpha<2$; In particular, for one sided Cauchy the norm could be as large as $n^2$.

Edit: The answer above deals with the spectral norm, not the spectral radius. However, in the case of good moment bounds of the entries, it also applies to the spectral radius. This is due to separation of eigenvalues of the matrix $A$, and in particular the fact that the top eigenvalue of $A$ (which equals $cn$) is separated from other eigenvalues of $A$ $(=0)$ by more than twice the norm of $W$. See e.g. Theorem 2 of Schonhage's paper http://www.sciencedirect.com/science/article/pii/002437957990154X (with k=m=n) and references there to earlier work.

$\endgroup$
4
  • 1
    $\begingroup$ I don't understand the first sentence. $X+EY$ is not the same as $|X|$. $\endgroup$ Jun 20, 2017 at 11:01
  • 1
    $\begingroup$ Sorry it was a typo (I called the zero mean matrix $X$, forgetting that $X$ was already defined in the OP). Fixed now. $\endgroup$ Jun 20, 2017 at 11:07
  • $\begingroup$ @oferzeitouni: I'm interested in the spectral radius, not the spectral norm. $\endgroup$ Jun 20, 2017 at 16:47
  • $\begingroup$ OOPS, my bad, I misread. Luckily, the answer is similar for the spectral radius, see edit. $\endgroup$ Jun 21, 2017 at 3:18
3
$\begingroup$

The spectral radius of a nonnegative matrix lies between the minimum and maximum row sums. Depending on the properties of $Y$, the sum of $n$ independent copies of $Y$ (i.e. any particular row sum) is likely to be concentrated near $n\,\mathbb EY$, so the spectral radius is also concentrated near $n\,\mathbb EY$. Exactly how near to $n\,\mathbb EY$ depends on the properties of $Y$ again. The width of the interval will be something like $n^{1/2}\log n$ times the standard deviation of $Y$ if $Y$ has a thin tail, though maybe a smaller interval can be proved.

See here for some relevant material. It would be interesting to know if Thm 1.2 can be used to prove sharper concentration. Probably this is all done before.

$\endgroup$
1
$\begingroup$

One relevant paper seems to be

Tao, Terence; Vu, Van; Krishnapur, Manjunath, Random matrices: universality of ESDs and the circular law, Ann. Probab. 38, No. 5, 2023-2065 (2010). ZBL1203.15025.

Which seems to indicate that under mild technical conditions for iid entries, the spectral measure (normalized by $1/\sqrt{n}$ converges to uniform in the unit disk. However, this tells us nothing about the spectral radius. Indeed, one right model for matrices for non-negative entries is as the adjacency matrix of a random $k$-regular graph (possibly for $k$ growing with $n,$ like $k=n/2$). Here, the spectral radius will be exactly $n/2,$ while the spectral measure will obey the Kesten-McKay-(Wigner) semicircle law.

$\endgroup$
0
$\begingroup$
  1. Yes, if that is the distribution you want for the entries.
  2. This will depend on the distribution; in most cases (other than finite discrete distributions) where the answer is finite, there will be no closed-form expression. For example, for a $2 \times 2$ matrix with nonnegative entries $$ \pmatrix{a & b\cr c & d}$$ the spectral radius is $(a + d + \sqrt{(a-d)^2 + 4 b c})/2$.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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