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$
  • $\begingroup$ @AnthonyQuas That can't be right, the spectral radius is at least the minimum row sum. $\endgroup$ – Brendan McKay Jun 16 '17 at 23:25
  • $\begingroup$ Oops. Yes. I agree. And of course what you're saying is the right asymptotic. $\endgroup$ – Anthony Quas Jun 17 '17 at 0:11
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$
  • 1
    $\begingroup$ I don't understand the first sentence. $X+EY$ is not the same as $|X|$. $\endgroup$ – Brendan McKay Jun 20 '17 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$ – ofer zeitouni Jun 20 '17 at 11:07
  • $\begingroup$ @oferzeitouni: I'm interested in the spectral radius, not the spectral norm. $\endgroup$ – Pietro Paparella Jun 20 '17 at 16:47
  • $\begingroup$ OOPS, my bad, I misread. Luckily, the answer is similar for the spectral radius, see edit. $\endgroup$ – ofer zeitouni Jun 21 '17 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, privacy policy and cookie policy

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