## Prove log of eigenvalues are dense in R?

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

Suppose you have the set of all possible $n$ x $n$ square adjacency matrices where $n$={1,2,3,4...}. For each matrix, compute the logarithm of the largest eigenvalue. Is it true that the set of logarithms you obtain is dense in $\mathbb{R}$? How do you begin to prove/disprove this?

-
adjacency matrices means entries are either 0 or 1? – 36min Sep 20 at 5:33

1
What is an adjacency matrix to you? Does it have to have only entries of $0$ or $1$? Does it have to have zeroes along the diagonal? Does it have to be symmetric? – Qiaochu Yuan Sep 20 at 5:52
Yes, it only has to have entries of $0$ or $1$. – Ivy Sep 20 at 7:50

1
See also this question: mathoverflow.net/questions/23989/… – Felix Goldberg Sep 20 at 8:54

## 2 Answers

I think you mean dense in $[0,\infty)$, since the spectral radius of a nonnegative integer matrix must be at least 1 (the product of all nonzero eigenvalues must be a nonzero integer). You are effectively asking whether Perron numbers are dense in $[1,\infty)$, and this is easy to see. For example, let $A_n$ be the companion matrix of $x^n-x-1$ and $\lambda_n$ be its spectral radius. It's easy to check that $\log \lambda_n\to 0$, and that $k \log \lambda_n =\log \lambda_n^k$ is the spectral radius of $A_n^k$, so these numbers, as $n, k=1,2,3,\dots$ are dense. Finally, one can recode the nonnegative integer matrix $A_n^k$ to an larger adjacency matrix with the same spectral radius using the standard idea called "higher block presentation" from symbolic dynamics (this is described in my book with Marcus called "An Introduction to Symbolic Dynamics and Coding").

-
I think you mean "I think you mean dense in $[1, \infty )$", right? ;) – Qfwfq Sep 20 at 8:45

1
I think $[0,\infty)$ is right because the OP asked about the logarithms of the largest eigenvalues. – Andreas Blass Sep 20 at 13:20
Oh yes, sure ! – Qfwfq Sep 20 at 17:15

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

In addition to Doug's nice answer above: it is probably even easier to show that the set of simple Parry numbers is dense in $(1,\infty)$. More precisely, let $\beta>1$ and let $(d_n)_{n=1}^\infty$ be the greedy $\beta$-expansion of 1, i.e., $$1=\sum_{n=1}^\infty d_n\beta^{-n},$$ where $d_1=\lfloor \beta\rfloor, d_2=\lfloor\beta\ \text{frac}(\beta) \rfloor, d_3=\lfloor \beta\ \text{frac}(\text{frac}(\beta))\rfloor$, etc. (Here $\lfloor\cdot\rfloor$ stands for the integer part and frac$(\cdot)$ for the fractional part.)

A number $\beta$ is called a simple Parry number (also known as a simple $\beta$-number) if $(d_n(\beta))_1^\infty$ has only a finite number of nonzero terms (i.e., ends with $0^\infty$). It is known that any Parry number is a Perron number; also, it is obvious that the Parry numbers are dense, since for any $\beta$ with an infinite $(d_n(\beta))_1^\infty$ we can truncate this sequence at any term and get a $d_n(\beta')$ for some simple Parry number $\beta'$. Since $(d_n(\beta))_1^\infty$ and $d_n(\beta')_1^\infty$ are close (in the topology of coordinate-wise convergence), so are $\beta$ and $\beta'$.

For more details and some references you may read the first couple of pages of this paper, for instance.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 39, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9316163659095764, "perplexity_flag": "head"}