---
abstract: 'This paper provides a new proof of a theorem of Chandler-Wilde, Chonchaiya and Lindner that the spectra of a certain class of infinite, random, tridiagonal matrices contain the unit disc almost surely. It also obtains an analogous result for a more general class of random matrices whose spectra contain a hole around the origin. The presence of the hole forces substantial changes to the analysis.'
author:
- |
    S N Chandler-Wilde\
    E B Davies
date: December 2011
title: |
    Spectrum of a Feinberg-Zee\
    Random Hopping Matrix
---

Mathematics Subject Classification: 65F15, 15A18, 15A52, 47A10, 47A75, 47B80, 60H25.

Key Words: spectrum, random matrix, hopping model, tridiagonal matrix, non-self-adjoint operator.

Introduction {#intro}
============

Over the last fifteen years there have been many studies of the spectral properties of non-self-adjoint, random, tridiagonal matrices $A$, some of them cited in [@CCM; @FZ1; @FZ2; @HOZ]. It has become clear that if all of the off-diagonal entries $A_{i,j}$ with $i-j=\pm 1$ of the matrices concerned are positive, the almost sure limit as $N\to\infty$ of the spectra of random $N\times N$ matrices subject to periodic boundary conditions can be quite different from the spectral behaviour of the corresponding infinite random matrix, [@EBD0; @EBD1; @GK1; @GK2]. Indeed the limit in the first case can be the union of a small number of simple curves, while the second limit has a non-empty interior.

Numerical calculations suggest that the situation is quite different if the off-diagonal entries have variable signs, but much less has been proved in this situation, which is the one that we consider here. In a recent paper, [@CCL], Chandler-Wilde, Chonchaiya and Lindner made important progress in determining the almost sure spectrum of a remarkably interesting class of non-self-adjoint, random, tridiagonal matrices introduced by Feinberg and Zee in [@FZ1], and sometimes called random hopping matrices, because the diagonal entries all vanish. Specifically they proved that, contrary to earlier conjectures, the infinite, tridiagonal matrix $$A_c= \left(\begin{array}{cccccc}
\ddots&\ddots&&&&\\
\ddots&0&1&&&\\
&c_{n-1}&0&1&&\\
&&c_n&0&1&\\
&&&c_{n+1}&0&\ddots\\
&&&&\ddots&\ddots\\
\end{array}\right)$$ has spectrum that contains the unit disc almost surely, [@CCL]. The paper assumed that the entries $c_n$ are independent and identically distributed with values in $\{\pm 1\}$.

In the present paper we assume that the entries $c_n$ are independent and identically distributed with values in $\{\pm
{\sigma}\}$ for some fixed ${\sigma}\in (0,1]$. We assume that the probability $p$ that $c_n={\sigma}$ satisfies $0<p<1$; the corresponding probability measure on ${\Omega}_{\sigma}=\{\pm {\sigma}\}^{{\bf Z}}$ is denoted by $\mu$. The matrix $A_c$ is identified with the bounded operator acting in the natural manner on $\ell^2({{\bf Z}})$.

In Lemma \[lemmaA\] we prove that $${{\rm Spec}}(A_c)\subseteq \{ {\lambda}: 1-{\sigma}\leq |{\lambda}|\leq 1+{\sigma}\}$$ by a perturbation argument. We also prove that $${{\rm Spec}}(A_c)\subseteq \{ x+iy:|x|+|y|\leq \sqrt{2(1+{\sigma}^2)}\}$$ by obtaining a bound on the numerical range of $A_c$. There are currently no general techniques for identifying the precise forms of holes in the spectra of non-self-adjoint operators, and we have not done so here, but numerical calculations are consistent with the hypothesis that it is the intersection, $H_{\sigma}$, of two elliptical regions as defined in (\[Hsigma\]); see the figures at the end of Section \[firstproof\]. Little is known about the part of the spectrum of $A_c$ outside the unit disc even in the case ${\sigma}=1$, but numerical studies suggest that the boundary of the spectrum has a self-similar fractal structure in that case; [@CCL; @HOZ].

The main result of [@CCL], that the spectrum contains the unit disc almost surely, is for the case that ${\sigma}=1$, when there is no hole in the spectrum. It depends upon the identification of a particular sequence $c\in {\Omega}_1$ such that the equation $A_cf={\lambda}f$ has a bounded solution $f$ for every ${\lambda}\in {{\bf C}}$ such that $|{\lambda}|<1$.

Our Theorem \[maintheorem\] rederives the main result of [@CCL], in which ${\sigma}=1$, but depends on a certain operator identity introduced in the next section. Our main result, Theorem \[maintheorem3\], that the spectrum of $A_c$ contains that part of the unit disc which is not in $H_{\sigma}$, applies to all ${\sigma}\in (0,1)$. We give a second proof of this result in Theorem \[maintheorem6\], by combining some results for ${\sigma}=1$ with bounds on the Lyapunov exponents of certain transfer matrices. Both proofs depend, additionally, on results on the spectra of operators on $\ell^2({{\bf Z}})$ which have different periodic structures on the positive and negative half-axes. They also both depend on explicit spectral calculations which we are able to carry out for certain operators $A_c$ with $c$ having arbitrarily large period.

Our main results, as just stated, concern the spectrum of the (bi-)infinite matrix $A_c$. In a shorter final section we spell out implications for the spectra of the corresponding semi-infinite and finite matrices, illustrating these observations with computations of the finite matrix spectra. In particular we show, by applying recent results of Lindner and Roch [@LR10], that, unlike $A_c$, the semi-infinite matrix has no hole in its spectrum for ${\sigma}\in (0,1)$, but contains the unit disc for all ${\sigma}\in (0,1]$.

Let ${{\cal E}}_{\sigma}$ denote the set of all $c\in{\Omega}_{\sigma}$ that are pseudo-ergodic in the sense of [@EBD1]. Precisely, $c\in{{\cal E}}_{\sigma}$ if for every finite sequence $b:\{1,...,n\}\to\{\pm {\sigma}\}$ there exists $m\in{{\bf Z}}$ such that $b_r=c_{m+r}$ for all $r\in \{1,...,n\}$. Such sequences $c$ are easy to construct without any reference to probability theory. The following facts, proved in [@EBD1], and rederived in [@Li; @CWL] as an instance of the application of limit operator arguments, will be crucial in this paper.

\[quasiergodic\] If $b,\, c \in{{\cal E}}_{\sigma}$ then ${{\rm Spec}}(A_b)={{\rm Spec}}(A_c)$. Let $S_{\sigma}$ denote this set, which is the main object of study in the paper. If $c\in{\Omega}_{\sigma}$, then $c\in{{\cal E}}_{\sigma}$ almost surely with respect to the measure $\mu$. Finally $$S_{\sigma}= \bigcup_{b\in{\Omega}_{\sigma}} {{\rm Spec}}( A_b ).$$

To describe a further result we establish, for $N\in {{\bf N}}$ and $\sigma\in (0,1]$ let $\pi_{N,\sigma}$ denote the union of ${{\rm Spec}}(A_c)$ over all $c\in \Omega_\sigma$ that are periodic with period $\leq N$. Let $$\label{eq:piinf}
\pi_{\infty,{\sigma}} =  \bigcup_{N\in{{\bf N}}} \pi_{N,{\sigma}}.$$ One obvious implication of the above proposition is that $$\label{eq:pidef}
\pi_{\infty,{\sigma}} \subset S_\sigma.$$ As is well-known, the set $\pi_{N,\sigma}$ is the union of eigenvalues of $N\times N$ matrices. (Precisely, it is the union, over all sequences $c$ and all $|\alpha|=1$, of the eigenvalues of the matrix $A^{(N,\mathrm{per})}_{c,\alpha}$ defined in [(\[finitematrix2\])]{} below; see [(\[spectrumperiodic\])]{} and [@LOTS]. For another, equivalent characterisation see Lemma \[BIO\].) This simple observation is useful, in that it provides a method for computing what prove to be large subsets of $S_\sigma$, and will be one component in our arguments.

An interesting question is whether $\pi_{\infty,{\sigma}}$ is dense in $S_{\sigma}$. We do not answer this question one way or the other, but our method of proof of Theorem \[maintheorem\], showing that the unit disc is a subset of $S_1$, as a by-product, and with some additional argument, leads to a proof that $\pi_{\infty,1}$ is dense in the unit disc (Theorem \[denseness\]).

For the sake of simplicity we will, throughout the rest of the paper, omit the subscript ${\sigma}$ in our notations if ${\sigma}=1$. We use ${{\bf N}}$ and ${{\bf Z}}_+$, respectively, as our notations for the sets of positive and non-negative integers.

An abstract theorem {#abstract}
===================

In this section we present an abstract theorem that might be interesting in other contexts. It will be applied in Section \[main\].

Let $A$ be a bounded linear operator acting on the Hilbert space ${{\cal H}}$ and let ${{\cal H}}={{\cal H}}_e\oplus{{\cal H}}_o$ be an orthogonal decomposition of ${{\cal H}}$.

\[interchange\] If $A({{\cal H}}_e)\subseteq {{\cal H}}_o$ and $A({{\cal H}}_o)\subseteq {{\cal H}}_e$ then ${{\cal H}}_e$ and ${{\cal H}}_o$ are invariant under the action of $A^2$. If $B$ is the restriction of $A^2$ to ${{\cal H}}_e$ and $M$ is the restriction of $A^2$ to ${{\cal H}}_o$ then $${{\rm Spec}}(A^2)\backslash \{0\}={{\rm Spec}}(B)\backslash
\{0\}={{\rm Spec}}(M)\backslash \{0\}.\label{identity1}$$ If $A$ is invertible then $${{\rm Spec}}(A^2)={{\rm Spec}}(B)={{\rm Spec}}(M).\label{identity2}$$

The decomposition ${{\cal H}}={{\cal H}}_e\oplus{{\cal H}}_o$ allows one to write the operator $A$ in the form $$A={\left(\begin{array}{cc}0&X\\Y&0 \end{array}\right)}$$ where $X:{{\cal H}}_o\to{{\cal H}}_e$ and $Y:{{\cal H}}_e\to{{\cal H}}_o$. Therefore $$A^2={\left(\begin{array}{cc}XY&0\\0&YX \end{array}\right)}.\label{A2identity}$$ This implies that $B=XY$ and $M=YX$. The second identity in (\[identity1\]) follows by some simple algebra that holds for any pair of bounded operators $X$ and $Y$, and the first identity is a trivial consequence.

If $A$ is invertible then (\[A2identity\]) implies that $B$ and $M$ are also invertible; therefore (\[identity2\]) is equivalent to (\[identity1\]).

\[spectralequality\] Let ${{\cal H}}=\ell^2({{\bf Z}})$, let ${{\cal H}}_e$ be the closed subspace of sequences whose supports are contained in the set of even integers, and let ${{\cal H}}_o$ be the closed subspace of sequences whose supports are contained in the set of odd integers. Let $A$ be a bounded operator on ${{\cal H}}$ whose matrix satisfies $A_{r,s}= 0$ for all $r,\, s$ such that $|r-s|\not= 1$. Then $A({{\cal H}}_e)\subseteq {{\cal H}}_o$ and $A({{\cal H}}_o)\subseteq {{\cal H}}_e$. Moreover the identities $${{\rm Spec}}(A^2)={{\rm Spec}}(B)={{\rm Spec}}(M)$$ are valid in either of the following two cases.

1.  $|A_{r,s}|=1$ for all $r,\, s$ such that $|r-s|=1$;

2.  There exist constants ${\beta},\, {\gamma}$ such that $0<{\beta}<{\gamma}<\infty$ and $|A_{r,s}|\leq {\beta}$ if $r-s=1$ while $|A_{r,s}|\geq {\gamma}$ if $r-s=-1$.

\
**Case 1.** An elementary calculation establishes that there exists a sequence $f:{{\bf Z}}\to{{\bf C}}$ such that $Af=0$, $|f_{2n}|=1$ for all $n$ and $f_{2n+1}=0$ for all $n$, so that $A$ and $B$ are not invertible viewed as operators on $\ell^\infty({{\bf Z}})$, and thus not invertible as operators on $\ell^2({{\bf Z}})$ (see e.g. [@RRS Theorem 2.5.2]). So $0\in{{\rm Spec}}(A)$ and $0\in{{\rm Spec}}(B)$. Similarly there exists a sequence $f:{{\bf Z}}\to{{\bf C}}$ such that $Af=0$, $|f_{2n+1}|=1$ for all $n$ and $f_{2n}=0$ for all $n$. Hence $0\in{{\rm Spec}}(M)$. The result follows by combining this with (\[identity1\]).

**Case 2.** The operator $A_L$ associated with the matrix $$(A_L)_{r,s}=\begin{choices}
A_{r,s}&\mbox{ if $r-s=-1$},\\
0&\mbox{ otherwise},
\end{choices}$$ is invertible and satisfies ${\Vert}A_L^{-1}{\Vert}\leq {\gamma}^{-1}$. The operator $A_R=A-A_L$ satisfies ${\Vert}A_R{\Vert}\leq {\beta}$. Therefore $A$ is invertible with $${\Vert}A^{-1}{\Vert}={\Vert}A_L^{-1}(I+A_RA_L^{-1})^{-1}{\Vert}\leq \frac{{\gamma}^{-1}}{1-{\beta}/{\gamma}}=\frac{1}{{\gamma}-{\beta}}.$$ The proof is completed by applying [(\[identity2\])]{}.

The case ${\sigma}=1$ {#main}
=====================

The following lemma was noted in [@CCL].

\[symmetry\]

If $c\in{\Omega}$ then ${{\rm Spec}}(A_c)$ is invariant with respect to both of the maps ${\lambda}\to\overline{{\lambda}}$ and ${\lambda}\to -{\lambda}$. If ${\lambda}\in
S$ then $\overline{{\lambda}}$ and $i{\lambda}$ lie in $S$. Hence $S$ is invariant under the dihedral symmetry group $D_2$ generated by these two maps.

The invariance of ${{\rm Spec}}(A_c)$ under complex conjugation follows directly from the fact that $A_c$ has real entries. If $D$ is the diagonal matrix with entries $D_{r,r}=(-i)^r$ for all $r\in{{\bf Z}}$ then $DA_cD^{-1}=iA_{-c}$, so $${{\rm Spec}}(A_c)=i{{\rm Spec}}(A_{-c}).\label{irotate}$$ Iterating this identity yields ${{\rm Spec}}(A_c)=-{{\rm Spec}}(A_{c})$. This proves the first part of the lemma. The second part follows once one observes that $c\in  {{\cal E}}$ if and only if $-c\in{{\cal E}}$.

The formulae in (\[iteration\]) are related to those in [@CCL Prop. 2.1], in a way that we will make explicit in Section \[sec:maps\]. However, nothing resembling the following lemma appears in [@CCL].

\[square\] Given $b\in{\Omega}$, let $c={\Gamma}_+(b)\in{\Omega}$ be the unique sequence satisfying $$c_0=1, \hspace{2em} c_{2n}+c_{2n+1}=0, \hspace{2em}
c_{2n}c_{2n-1}=b_n,\label{iteration}$$ for all $n\in {{\bf Z}}$. Then $A_c^2$ is unitarily equivalent to $A_b\oplus M_b$ acting in $\ell^2({{\bf Z}})\oplus \ell^2({{\bf Z}})$, where $$(M_bf)_n=-f_{n-1}+(c_{2n+1}+c_{2n+2})f_n+f_{n+1}\label{Mbformula}$$ for all $f\in \ell^2({{\bf Z}})$. Moreover $${{\rm Spec}}(A_c^2) = {{\rm Spec}}(A_b)={{\rm Spec}}(M_b).$$

One may write $(A_cf)_n=c_nf_{n-1}+f_{n+1}$ for all $n\in {{\bf Z}}$, or equivalently $A_c=V_cR+L$ where $(Lf)_n=f_{n+1}$, $(Rf)_n=f_{n-1}$ and $(V_cf)_n=c_nf_n$ for all $f\in \ell^2({{\bf Z}})$.

Therefore $$\begin{aligned}
A_c^2&=& V_cRV_cR+LV_cR+V_cRL+L^2\\
&=& X_cR^2+Y_c+L^2\end{aligned}$$ where $X_c$ and $Y_c$ are the diagonal matrices with diagonal entries $$\begin{aligned}
X_{c,n,n}&=&c_nc_{n-1}, \\
Y_{c,n,n}&=& c_n+c_{n+1}.\end{aligned}$$ The operator $A_c^2$ has two invariant subspaces $${{\cal H}}_e=\{f\in \ell^2({{\bf Z}}):f_{2n+1}=0 \mbox{ for all } n\in{{\bf Z}}\}$$ and ${{\cal H}}_o=\ell^2({{\bf Z}})\ominus {{\cal H}}_e$. After an obvious relabeling of the subscripts, the restriction of $A_c^2$ to ${{\cal H}}_e$ equals $A_b$ while the restriction of $A_c^2$ to ${{\cal H}}_o$ is equal to $M_b$, as defined in (\[Mbformula\]). The final statement of the lemma is now an application of Theorem \[spectralequality\], case 1.

We will exploit extensively the formula ${{\rm Spec}}(A_c^2) = {{\rm Spec}}(A_b)$ which appears in the above lemma. The equation ${{\rm Spec}}(A_b)={{\rm Spec}}(M_b)$ will not play a role in our subsequent arguments, but makes an intriguing connection between spectra of rather different tridiagonal operators. Extending this connection slightly, for $b\in {\Omega}$ define $c={\Gamma}_+(b)$ and $\tilde M_b$ by $$(\tilde M_b f)_n =  f_{n-1} + i^n(c_{2n+1}+c_{2n+2}) f_n + f_{n+1},$$ for all $f\in \ell^2({{\bf Z}})$. Then, arguing as we do above to show [(\[irotate\])]{}, we see that $${{\rm Spec}}(\tilde M_b) = i\,{{\rm Spec}}(M_b).$$ In particular, in the case $b\in {{\cal E}}$ when, by Lemma \[symmetry\], $i{{\rm Spec}}(M_b)=i{{\rm Spec}}(A_b) = {{\rm Spec}}(A_b)$, we see that $$S = {{\rm Spec}}(A_b) = {{\rm Spec}}(\tilde M_b).$$ Thus, in studying $S$, we are studying both the almost sure spectrum of the infinite hopping-sign matrix $A_b$ with respect to the measure $\mu$, and the almost sure spectrum, with respect to the same measure, of $\tilde M_b$, a discrete Schrödinger operator with a particular, complex random potential.

In the next lemma we define the square root of any non-zero complex number to be the root whose argument lies in $(-\pi/2,\pi/2]$.

\[squareroot\] If $b\in{\Omega}$ and $c={\Gamma}_+(b)$ then ${\lambda}\in{{\rm Spec}}(A_b)$ if and only if $\pm\sqrt{{\lambda}}$ both lie in ${{\rm Spec}}(A_c)$. If ${\lambda}\in S$ then $\pm \sqrt{{\lambda}}$ both lie in $S$.

Lemma \[symmetry\] and Lemma \[square\] imply that the following statements are equivalent. ${\lambda}\in {{\rm Spec}}(A_b)$; ${\lambda}\in
{{\rm Spec}}(A_c^2)=\left( {{\rm Spec}}(A_c)\right)^2$; either $\sqrt{{\lambda}}$ or $-\sqrt{{\lambda}}$ lies in ${{\rm Spec}}(A_c)$; $\pm\sqrt{{\lambda}}$ both lie in ${{\rm Spec}}(A_c)$.

If ${\lambda}\in S$ and $b\in {{\cal E}}$ then ${\lambda}\in {{\rm Spec}}(A_b)$ by Proposition \[quasiergodic\]. Lemma \[square\] implies that $${\lambda}\in {{\rm Spec}}(A_c^2)=\left({{\rm Spec}}(A_c)\right)^2\subseteq S^2.$$ Therefore either $\sqrt{{\lambda}}$ or $-\sqrt{{\lambda}}$ lie in $S$. The proof is completed by applying Lemma \[symmetry\].

\[maintheorem\] The set $S$ contains $$\label{the_set}
\bigcup_{n\in{{\bf Z}}_+,\;
r\in \{0,...,2^{n+2}\}}\;{{\rm e}}^{\pi i r/2^{n+1}}\,[0,2^{1/2^n}] .$$ Hence $S$ contains the unit disc in ${{\bf C}}$.

For $n=0$ the theorem states that $$[0,2]\times\{ 1,i,-1,-i\}\subset S.$$ This follows by combining Lemma \[symmetry\] with direct calculations of ${{\rm Spec}}(A_c)$ when $c_n=1$ for all $n\in{{\bf Z}}$ (in which case ${{\rm Spec}}(A_c)=[-2,2]$) and when $c_n=-1$ for all $n\in{{\bf Z}}$ (in which case ${{\rm Spec}}(A_c)=i[-2,2]$). For larger $n$ the first statement of the theorem follows by applying Lemma \[squareroot\] inductively. The second statement is now a consequence of the fact that the set [(\[the\_set\])]{} is dense in the unit disc.

The maps ${\Gamma}_\pm$ {#sec:maps}
=======================

A crucial role has been played in the proofs above by the nonlinear map $\Gamma_+$ on ${\Omega}$ introduced in Lemma \[square\], and this map will be key to the arguments that we make throughout this paper. And in fact a sequence which is almost a fixed point of $\Gamma_+$ (in a sense made precise below Lemma \[spaceinversion\]) is central to the proof of Theorem \[maintheorem\] in [@CCL], though the proof is quite different and no mapping $\Gamma_+$ appears in [@CCL].

The relationship between the above proof of Theorem \[maintheorem\] and that in [@CCL] is clarified to some extent by the following. Building on the definition of $\Gamma_+$ made above, let us define maps ${\Gamma}_\pm:{\Omega}\to{\Omega}$ by ${\Gamma}_\pm (b)=c$ where $$c_0=\pm 1, \hspace{2em} c_{2n}+c_{2n+1}=0, \hspace{2em}
c_{2n}c_{2n-1}=b_n,\label{cfixed0}$$ for all $n\in{{\bf Z}}$. We also define the space inversion symmetry $b\to
{\widehat}{b}$ by ${\widehat}{b}_n=b_{1-n}$ for all $n\in{{\bf Z}}$.

\[spaceinversion\] If ${\Gamma}_\pm (b)=c$ then ${\Gamma}_\mp ({\widehat}{b})={\widehat}{c}$. In particular ${\Gamma}_\pm (c)=c$ if and only if ${\Gamma}_\mp ({\widehat}{c})={\widehat}{c}$. Each of the equations ${\Gamma}_\pm (c)=c$ has exactly one solution.

Let $c={\Gamma}_+(b)$ and $d={\Gamma}_-({\widehat}{b})$. Then $d_0=-1$, $d_{2n}+d_{2n+1}=0$ and $d_{2n}d_{2n-1}={\widehat}{b}_n=b_{1-n}$ for all $n\in{{\bf Z}}$. Therefore ${\widehat}{d}_0=d_1=1$. Also $${\widehat}{d}_{2n+1}+{\widehat}{d}_{2n}=d_{1-(2n+1)}+d_{1-2n}=d_{-2n}+d_{1-2n}=0$$ and $${\widehat}{d}_{2n}{\widehat}{d}_{2n-1}=d_{1-2n}d_{1-(2n-1)}=d_{2(1-n)-1}d_{2(1-n)}={\widehat}{b}_{1-n}=b_n$$ for all $n\in{{\bf Z}}$. Therefore ${\widehat}{d}={\Gamma}_+(b)=c$ and $d={\widehat}{c}$.

The proof that $c={\Gamma}_-(b)$ implies $d={\Gamma}_+({\widehat}{b})$ is similar. The other statements of the lemma follow immediately.

This paper and [@CCL] use three different special sequences. The sequences $c_\pm$ are defined by ${\Gamma}_\pm (c_\pm)=c_\pm$. It follows directly from their definitions that $c_{+,0}=1$ and $c_{+,1}=-1$ while $c_{-,0}=-1$ and $c_{-,1}=1$. However $$c_{+,n}=c_{-,n}=c_{+,1-n}=c_{-,1-n}$$ for all $n\not= 0,\, 1$. The paper [@CCL] uses the sequence $c_e$ such that $c_{e,0}=c_{e,1}=1$, while $c_{e,n}=c_{\pm,n}$ for all other $n$. Because of the space inversion symmetry the use of $c_+$ or $c_-$ in any proof is really a matter of convenience.

We now turn to the solution of the equation $A_c u={\lambda}u$ where $u:{{\bf Z}}\to{{\bf C}}$ is an arbitrary sequence. The eigenvalue equation is equivalent to the second order recurrence equation $$u_{n+1}+c_nu_{n-1}={\lambda}u_n.$$

\[uflip\] Suppose that $c\in{\Omega}$ and $\widehat{c}_n=c_{1-n}$ for all $n\in{{\bf Z}}$; that $u_{n+1}+c_nu_{n-1}={\lambda}u_n$ for some ${\lambda}\in{{\bf C}}$ and all $n\in{{\bf Z}}$ and $u_0=0$, $u_1=1$; and that $\widehat{u}_{n+1}+\widehat{c}_n\widehat{u}_{n-1}={\lambda}\widehat{u}_n$ for all $n\in{{\bf Z}}$ and $\widehat{u}_0=0$, $\widehat{u}_1=1$. Then $|\widehat{u}_{n}|=|u_{-n}|$ for all $n\in{{\bf Z}}$. In particular $u_n$ is bounded as $n\to\infty$ if and only if $\widehat{u}_n$ is bounded as $n\to -\infty$.

If one puts $v_n=u_{-n}$ then $$\widehat{c}_{n+1}v_{n+1}+v_{n-1}=c_{-n}u_{-n-1}+u_{-n+1}={\lambda}u_{-n}={\lambda}v_n \label{growthlemma}$$ for all $n\in{{\bf Z}}$. Define $a:{{\bf Z}}\to\{\pm 1\}$ by $a_0=1$ and $a_n/a_{n-1}=\widehat{c}_n$ for all $n\in{{\bf Z}}$. If one now puts $w_n=a_n v_n$ for all $n\in{{\bf Z}}$ then (\[growthlemma\]) implies $$w_{n+1}+\widehat{c}_nw_{n-1}={\lambda}w_n$$ for all $n\in{{\bf Z}}$. Since $w_0=v_0=u_0=0$ it follows that there exist ${\gamma}$ such that $w_n={\gamma}\widehat{c}_n$ for all $n\geq 1$. But $|c_n|=1$ for all $n$, so one obtains $|{\gamma}|=1$ by evaluating this identity for $n=1$. Therefore $|\widehat{u}_n|=|w_n|=|v_n|=|u_{-n}|$ for all $n\geq 1$.

\[uevenodd\] Let $u_+,\, u_-,\, u_e:{{\bf Z}}\to {{\bf C}}$ be the solutions of $u_{n+1}+c_nu_{n-1}={\lambda}u_n$ for all $n\in{{\bf Z}}$ subject to $u_0=0$ and $u_1=1$, if $c$ is put equal to $c_+,\, c_-,\, c_e$ respectively. Then $u_{+,n}=u_{e,n}$ for all $n\in{{\bf Z}}$. Moreover $|u_{-,n}|=| u_{e,n}|$ for all $n\in{{\bf Z}}$.

The first statement is proved by an elementary computation. For the second we use $c_e=\widehat{c_e}$ and $c_-=\widehat{c_+}$. Lemma \[uflip\] now yields $$|u_{-,n}|=|u_{+,-n}|=|u_{e,-n}|=|u_{e,n}|$$ for all $n\in{{\bf Z}}$.

The main step in the proof of Theorem \[maintheorem\] in [@CCL] is contained in the following proposition (we quote here the parts of [@CCL Proposition 2.1] which we use immediately or later in section \[secondproofsection\]).

\[CCLprop\] Let $u_e$ be defined as in Corollary \[uevenodd\] and define $p_{i,j}\in {{\bf Z}}$ for $i,j\in{{\bf N}}$ by the formula $$u_{e,i}=\sum_{j=1}^i p_{i,j}{\lambda}^{j-1}$$ with $p_{i,j}=0$ if $j>i$. Let $Y$ denote the set of $(i,j)\in {{\bf N}}^2$ such that $p_{i,j}\neq 0$. Then $p_{i,j}\in\{0,1,-1\}$ for all $i,\, j$ and $(i,j)\in Y$ if and only if one of the following holds.\
(1) $i=j=1$;\
(2) $i$ and $j$ are both even and $(i/2,j/2)\in Y$;\
(3) $i$ and $j$ are both odd and $((i+1)/2,(j+1)/2)\in Y$;\
(4) $i$ and $j$ are both odd and $((i-1)/2,(j+1)/2)\in Y$.

The following result is an immediate corollary of this proposition and Corollary \[uevenodd\], which together imply that $|u_{e,i}|\leq (1-|\lambda|)^{-1}$ for $i\in {{\bf Z}}$ and $|\lambda|<1$.

[@CCL] \[CCLprop3\] As in Corollary \[uevenodd\], let $u_e:{{\bf Z}}\to {{\bf C}}$ be the solution of $u_{n+1}+c_nu_{n-1}={\lambda}u_n$ for all $n\in{{\bf Z}}$ subject to $u_0=0$ and $u_1=1$, with $c=c_e$. Then $u_e\in \ell^\infty({{\bf Z}})$ for $|{\lambda}|<1$, so that ${{\rm Spec}}(A_{c_e})$ contains the unit disc.

Since Corollary \[uevenodd\] has shown that $u_{+}=u_{e}$, it is clear from Theorem \[CCLprop3\] that ${{\rm Spec}}(A_{c_+})$ also contains the unit disc. In fact this is precisely its spectrum.

\[c+spectrum\] If $c_+$ is the unique solution of ${\Gamma}_+(c)=c$ then $${{\rm Spec}}(A_{c_+})=\{ z:|z|\leq 1\}.$$

It remains only to show that ${{\rm Spec}}(A_{c_+})\subset\{ z:|z|\leq 1\}$. If ${\lambda}\in {{\rm Spec}}(A_{c_+})$ then repeated applications of the first part of Lemma \[squareroot\] yield ${\lambda}^{2^n}\in {{\rm Spec}}(A_{c_+})$ for all $n\geq 1$. Since the spectrum is a bounded set, it follows that $|{\lambda}|\leq 1$.

We will (rather arbitrarily) focus on the mapping $\Gamma_+$ rather than $\Gamma_-$ in the remainder of the paper. The following lemma, which shows that the set of periodic sequences is invariant under the action of ${\Gamma}_{+}$, will play a key role.

\[lem\_periodic\] If $b\in \Omega$ is periodic with period $N$, i.e. $b_{n+N} = b_n$, $n\in{{\bf Z}}$, then $c={\Gamma}_{+}(b)$ is $4N$-periodic. Conversely, if $b\in\Omega$, $c={\Gamma}_{+}(b)$, and $c$ is $2N$-periodic for some $N\in{{\bf N}}$, then $b$ is $N$-periodic.

First note that, if $c={\Gamma}_{+}(b)$ and one defines $\tilde c\in
\Omega$ by $\tilde c_n=c_{2n}$, $n\in{{\bf Z}}$, then $$c={\Gamma}_{+}(b) \Leftrightarrow (\tilde c_0=1, \quad \tilde c_n =
-b_n \tilde c_{n-1}, \; c_{2n+1} = - \tilde c_n, \;
n\in{{\bf Z}}).\label{equiv}$$ Therefore $$\tilde c_{m+n} = \tilde c_m\,(-1)^n\prod_{j=1}^n
b_{m+j}\label{equiv2}$$ for all $m\in{{\bf Z}}$ and $n\in{{\bf N}}$. If $b$ is $N$-periodic, then $$\tilde c_{m+2N} = \tilde c_m\,\prod_{j=1}^{2N} b_{m+j} =
\tilde c_m\,\prod_{j=1}^{N} b_{m+j}^2 = \tilde c_m,$$ for all $m\in{{\bf Z}}$. Therefore $c$ is $4N$-periodic.

Conversely, if $c={\Gamma}_{+}(b)$, for some $b\in
\Omega$, and $c$ is $2N$-periodic for some $N\in{{\bf N}}$, then $\tilde c$ is $N$-periodic and, from [(\[equiv\])]{}, it follows that $b$ is $N$-periodic.

To illustrate the above lemma, define $c^-,c^+ \in {\Omega}$ by $c^-_n =  -1$, $c^+_n=1$, for $n\in{{\bf Z}}$, and define the sequences $c^{(m,+)}, c^{(m,-)}\in {\Omega}$, for $m=0,1,...$, by $$\label{periodic_sequences}
c^{(0,\pm)} = c^\pm, \quad c^{(m,\pm)} = \Gamma_+(c^{(m-1,\pm)}), \quad m\in {{\bf N}}.$$ Then explicit calculations of the action of $\Gamma_+$ yield that $c^{(1,+)}={\Gamma}_{+}(c^+)$ is $4$-periodic (but not periodic with any smaller period), with $c^{(1,+)}_{-1}=c^{(1,+)}_0=1$, $c^{(1,+)}_1=c^{(1,+)}_2=-1$. On the other hand, $c^{(1,-)}={\Gamma}_{+}(c^-)$ is $2$-periodic (and so also $4$-periodic), with $c^{(1,-)}_n = (-1)^n$ for all $n\in{{\bf Z}}$.

Both these calculations, of course, are consistent with the lemma, which implies that $c^{(m,\pm)}$ is $N$-periodic with $N=4^m$, so that, using the notation [(\[eq:piinf\])]{} (dropping ${\sigma}$ given that ${\sigma}=1$), $$\label{inclusion}
{{\rm Spec}}(A_{c^{(m,\pm)}}) \subset \pi_{4^m}, \quad m=0,1,... .$$

Although we do not have an explicit formula for the sequences $c^{(m,\pm)}$, it is easy to compute ${{\rm Spec}}(A_{c^{(m,\pm)}})$. By Lemma \[squareroot\], if $c=\Gamma_+(b)$, then $$\label{speciter}
{{\rm Spec}}(A_c) = \{\pm \sqrt{\lambda}: \lambda \in {{\rm Spec}}(A_b)\}.$$ The proof of Theorem \[maintheorem\] begins with the observation that ${{\rm Spec}}(A_{c^+})=[-2,2]$ and ${{\rm Spec}}(A_{c^-})=i[-2,2]$. Combining this observation with [(\[speciter\])]{} we easily prove by induction that $$\label{spec_cplus}
{{\rm Spec}}(A_{c^{(m,+)}}) = \left\{r\,{{\rm e}}^{\pi i j/2^{m}}: 0\leq r \leq 2^{1/2^m}, \;j\in \{0,...,2^{m+1}-1\}\right\}$$ and $$\label{spec_cminus}
{{\rm Spec}}(A_{c^{(m,-)}}) ={{\rm e}}^{\pi i/2^{m+1}}\,{{\rm Spec}}(A_{c^{(m,+)}}).$$

Combining equations [(\[inclusion\])]{}, [(\[spec\_cplus\])]{} and [(\[spec\_cminus\])]{}, we see that we have shown that $$\left\{r\,{{\rm e}}^{\pi i j/2^{m}}: 0\leq r \leq 2^{1/2^{m+1}}, \;j\in \{0,...,2^{m+2}-1\}\right\}\subset \pi_{4^m}, \quad m=0,1,... .$$ Thus we have shown the following modification of Theorem \[maintheorem\] which, of course, by [(\[eq:pidef\])]{}, has Theorem \[maintheorem\] as a corollary.

\[denseness\] The set $\pi_\infty$ contains the set [(\[the\_set\])]{}, and so is dense in the unit disc in ${{\bf C}}$.

We know ${{\rm Spec}}(A_{c^{(m,\pm)}})$ explicitly, but do not have explicit formulae for the sequences $c^{(m,\pm)}$. However we can show that $c^{(m,\pm)}$ converges pointwise to the sequence $c_+$, the unique fixed point of $\Gamma_+$, as $m\to \infty$. This is the content of the next two lemmas. We omit a proof of the first of these lemmas which is an easy consequence, by simple induction arguments, of the definition of ${\Gamma}_+$.

\[maplem\] If $b\in\Omega$ and $c=\Gamma_+(b)$, then $c_0=c_{+,0}$ and $c_1 =c_{+,1}$. If, for some $N\in{{\bf N}}$, $b_m=c_{+,m}$ for $m = 1,...,N$, then also $c_m = c_{+,m}$ for $m = 2,...,2N+1$. If, for some $N\in{{\bf Z}}_+$, $b_{-m}=c_{+,-m}$ for $m = 0,1,...,N$, then $b_{-m}=c_{+,-m}$ for $m = 1,2,...,2N+2$.

\[strong\_converg\] Let $b \in\Omega$, and define $c^{(n)}\in {\Omega}$ for $n\in {{\bf N}}$ by $c^{(1)}={\Gamma}_+(b)$ and $c^{(n+1)} = {\Gamma}_+(c^{(n)})$, $n\in{{\bf N}}$. Then, for $n\in{{\bf N}}$, $$c^{(n)}_m = c_{+,m}, \quad m = 2-2^n,3-2^n,...,2^n-1,$$ so that $c^{(n)}\to c_+$ pointwise and $A_{c^{(n)}}$ converges strongly to $A_{c_+}$ as $n\to\infty$. Further, $${{\rm Spec}}(A_{c^{(n)}}) \subset \{\lambda: |\lambda|\leq 2^{1/2^n}\}.$$

The first equation follows by induction from Lemma \[maplem\]. The second equation follows by induction from [(\[speciter\])]{} and the trivial bound that ${{\rm Spec}}(A_b)\subset \{\lambda:|\lambda|\leq 2\}$, which holds for all $b\in {\Omega}$.

The mapping $\Gamma_{{\sigma},+}$ {#related}
=================================

For the rest of the paper we consider operators $A_c$ for which the coefficients $c_n$ take values in $\{\pm {\sigma}\}$, where $0<{\sigma}\leq
1$; that is, in the notation we have introduced in the introduction, we assume that $c\in \Omega_{\sigma}$, for some ${\sigma}\in (0,1]$.

The mapping $\Gamma_+$ that we have introduced continues to play an important role. We extend the mapping so that it operates on $\Omega_{{\sigma}^2}$, defining, for ${\sigma}\in (0,1]$, $\Gamma_{{\sigma},+}:\Omega_{{\sigma}^2}\to \Omega_{\sigma}$ by $$\label{def_Gam_sig_plus}
\Gamma_{{\sigma},+}(c) = {\sigma}\Gamma_+({\sigma}^{-2}c).$$ In other words, for $b\in \Omega_{{\sigma}^2}$, $c=\Gamma_{{\sigma},+}(b)$ is the unique sequence in $\Omega_{\sigma}$ satisfying $$c_0={\sigma}, \hspace{2em} c_{2n}+c_{2n+1}=0, \hspace{2em}
c_{2n}c_{2n-1}=b_n.\label{iteration2a}$$

Main properties of the mapping $\Gamma_{{\sigma},+}$ for our purposes are contained in the following extension of Lemma \[squareroot\]. We will need to refer to a number of circular annuli, and use in this lemma and subsequently the notation $$\label{annuli}
{ [ \hspace*{-0.15em} [   a,b  ] \hspace*{-0.15em} ] } =\{ {\lambda}:a\leq |{\lambda}|\leq b\}.$$

\[lemmaB\]If $b\in{\Omega}_{{\sigma}^2}$ and $c={\Gamma}_{{\sigma},+}(b)\in {\Omega}_{\sigma}$, then $$(\,{\lambda}\in {{\rm Spec}}(A_b) \,)\Leftrightarrow (\, \pm \sqrt{{\lambda}} \in
{{\rm Spec}}(A_c) \,).\label{sigmaroot0}$$ Hence $$(\,{\lambda}\in S_{{\sigma}^2}\,){\Rightarrow}(\, \pm \sqrt{{\lambda}} \in
S_{\sigma}\,)\label{sigmaroot}$$ and $$(\, { [ \hspace*{-0.15em} [ a,b ] \hspace*{-0.15em} ] }\subseteq S_{{\sigma}^2}\,){\Rightarrow}( \, { [ \hspace*{-0.15em} [ a^{1/2},b^{1/2} ] \hspace*{-0.15em} ] }\subseteq S_{{\sigma}}\,).\label{sigroot2}$$

We modify the calculations in Section \[main\]. Lemma \[symmetry\] is valid as it stands. In Lemma \[square\] we assume that $b\in {\Omega}_{{\sigma}^2}$, and define $c\in {\Omega}_{\sigma}$ by $c={\Gamma}_{{\sigma},+}(b)$, and apply Case 2 of Theorem \[spectralequality\] in place of Case 1. This leads to the conclusion ${{\rm Spec}}(A_c^2)= {{\rm Spec}}(A_b)$ as in Lemma \[squareroot\]. (\[sigmaroot\]) and (\[sigroot2\]) follow by choosing $b\in{{\cal E}}_{{\sigma}^2}$ and using Proposition \[quasiergodic\].

Periodic and paired periodic operators {#periodic_ops}
======================================

To prove our main theorem we need results on operators $A_c$ on $\ell^2({{\bf Z}})$ that have one periodic structure for $n\geq 0$ and another for $n<0$ (which we term paired periodic operators). The essential spectrum of such an operator is the union of the essential spectra of the periodic operators involved, which may be calculated explicitly using their Bloch decompositions.

There may also be substantial inessential spectrum, in particular, open subsets of the spectrum where $A_c-{\lambda}I$ is Fredholm but has non-zero index. These parts of the spectrum (and the corresponding values of the index) can be computed by application of general results for block Toeplitz operators, which have been developed to a high degree of sophistication; see [@B2; @BS; @BK; @BS2] and the references therein. We need only a small part of this theory, and it is easy to develop this from first principles. We do this in a short Lemma \[lem\_two\_periods\] below, inspired by earlier analysis in [@DS; @EBD0; @EBD1], and particularly [@EBD1 Theorem 12]. Both the proof of Lemma \[lem\_two\_periods\], and the effective application of this lemma to prove Theorem \[maintheorem3\], depend on the next two lemmas which describe properties of the spectra and eigenfunctions of periodic operators.

We assume throughout this section that the parameter ${\sigma}\in (0,1)$.

\[quadraticbounds\] Let $$\Phi(\tau,{\gamma})= \frac{{{\rm Re}}(\tau)^2}{(1+{\gamma})^2}+
\frac{{{\rm Im}}(\tau)^2}{(1-{\gamma})^2}\label{Phidef}$$ where $\tau\in{{\bf C}}$ and $-1< {\gamma}<1$. Then the quadratic equation $$z^2-\tau z+{\gamma}=0\label{zeq}$$ has a solution satisfying $|z|=1$ if and only if $\Phi=1$. If $\Phi<1$ then both solutions satisfy $|z|<1$. If $\Phi>1$ then one solution satisfies $|z|<1$ and the other satisfies $|z|>1$.

For $\theta\in{{\bf R}}$, $z={{\rm e}}^{i\theta}$ is a solution of (\[zeq\]) if and only if $$\cos(\theta)=\frac{{{\rm Re}}(\tau)}{1+{\gamma}}, \hspace{2em}
\sin(\theta)=\frac{{{\rm Im}}(\tau)}{1-{\gamma}},$$ so that [(\[zeq\])]{} has a solution satisfying $|z|=1$ if and only if $\Phi(\tau,\gamma)=1$.

The set $U=\{\tau\in{{\bf C}}:\Phi<1\}$ is connected and contains the origin. Since the solutions of (\[zeq\]) depend continuously on $\tau$, and both solutions satisfy $|z|<1$ if $\tau=0$, it follows that both satisfy $|z|<1$ for all $\tau\in U$. The case $\Phi>1$ is similar.

The following lemma is closely related to a similar result for the non-self-adjoint Anderson model in [@EBD1 Theorem 11].

\[BIO\] If $c\in {\Omega}_{\sigma}$ and ${\lambda}\in {{\bf C}}$ then the space of all solutions of $A_cf={\lambda}f$ is two-dimensional. If $c$ is periodic with period $p$ then the asymptotic behaviour as $n\to\pm\infty$ of the solutions is determined by the solutions $z_1,\, z_2$ of the polynomial $z^2-\tau({\lambda}) z+{\gamma}=0$, where $\tau({\lambda})$ is a monic polynomial in ${\lambda}$ with degree $p$, given by $\tau(\lambda) = {{\rm tr}}(T_p)$, where $T_p=X_p X_{p-1}\ldots X_1$ and $$X_n = {\left(\begin{array}{cc}0&1\\ -c_n&{\lambda}\end{array}\right)},$$ and ${\gamma}=\det(T_p)=\pm {\sigma}^p$. Ordering the two solutions so that $|z_1|\geq |z_2|$, there are three cases:

1.  $\lambda$ lies in the closed set $$B_c=\{{\lambda}: |z_1|=1\mbox{ and } |z_2|={\sigma}^p\}.$$ This set is the spectrum of $A_c$, equivalently, the set of ${\lambda}$ for which $A_cf={\lambda}f$ has a bounded solution.

2.  ${\lambda}$ lies in the open set $$I_c=\{{\lambda}: 1> |z_1|\geq|z_2|>{\sigma}^p\}.$$ This is the case if and only if all solutions of $A_cf={\lambda}f$ decay exponentially as $n\to +\infty$.

3.  ${\lambda}$ lies in the open set $$O_c=\{{\lambda}: |z_1|>1\mbox{ and } |z_2|<{\sigma}^p\}.$$ This is the case if and only if there exists a solution of $A_cf={\lambda}f$ that decays exponentially as $n\to +\infty$ and grows exponentially as $n\to
    -\infty$, and another solution that decays exponentially as $n\to
    -\infty$ and grows exponentially as $n\to +\infty$.

The sequence $f:{{\bf Z}}\to{{\bf C}}$ is a solution of $A_cf={\lambda}f$ if and only if $f_{n+1}+c_n f_{n-1}={\lambda}f_n$ for all $n\in{{\bf Z}}$. This recurrence relation can be rewritten in the form $$\begin{aligned}
{\left(\begin{array}{c} f_n\\ f_{n+1} \end{array}\right)}&=&{\left(\begin{array}{cc}0&1\\ -c_n&{\lambda}\end{array}\right)}{\left(\begin{array}{c} f_{n-1}\\ f_n \end{array}\right)}\\
&=& X_n{\left(\begin{array}{c} f_{n-1}\\ f_n \end{array}\right)}\\
&=& T_n{\left(\begin{array}{c} f_{0}\\ f_1 \end{array}\right)}\end{aligned}$$ where $T_n=X_n X_{n-1}\ldots X_1$. If $c$ is periodic with period $p$, then the asymptotic behaviour of the two-dimensional space of eigenfunctions $f$ is determined by the magnitude of the eigenvalues $z_1,\, z_2$ of $T_p$. These are the solutions of the equation $z^2-\tau z+{\gamma}=0$ where $\tau={{\rm tr}}(T_p)$ and ${\gamma}=\det(T_p)$. A simple induction establishes that the $(i,j)$-th entry of $T_p$ is a polynomial in ${\lambda}$ with degree less than $p$ unless $i=j=2$ in which case it is a monic polynomial with degree $p$. Therefore $\tau$ is a monic polynomial in ${\lambda}$ with degree $p$. However $$\det(T_p)=\prod_{r=1}^p \det(X_r)= c_1 \dots c_p = \pm {\sigma}^p$$ does not depend on ${\lambda}$. The continuous dependence of the roots of a polynomial on its coefficients implies that $B_c$ is closed while $I_c$ and $O_c$ are open. An application of Lemma \[quadraticbounds\] now completes the proof. One sees, in particular, that $${{\rm Spec}}(A_c)= B_c=\{{\lambda}: \Phi(\tau,{\gamma})=1 \}.$$

Our next lemma enables us to determine the sets $I_c$ and $O_c$ for certain important periodic sequences $c$, and to determine the spectra of certain paired periodic operators. We continue with the assumptions and notation of Lemma \[BIO\].

\[findIcOc\] If $V$ is a connected component of ${{\bf C}}\backslash B_c$ then $V\subseteq I_c$ or $V\subseteq O_c$. If $V$ is unbounded then $V\subseteq O_c$, and if $0\in V$ then $V\subseteq I_c$. If ${{\bf C}}\backslash B_c$ has exactly two components then the bounded component equals $I_c$ and the unbounded component equals $O_c$.

We first observe that $V$, $I_c$ and $O_c$ are all open sets and that their definitions imply directly that $I_c,\, O_c$ are disjoint. Therefore $V=(V\cap I_c)\cup (V\cap O_c)$, where the two intersections on the right-hand side are disjoint. Since $V$ is connected, it follows that $V=V\cap I_c$ or $V=V\cap O_c$ This completes the proof of the first statement.

Lemma \[BIO\] case 1 implies that $$B_{\sigma}={{\rm Spec}}(A_c)\subseteq \{{\lambda}: |{\lambda}|\leq 1+{\sigma}\}.$$ Therefore ${{\bf C}}\backslash B_c$ has only one unbounded component $V$ and it contains $\{ {\lambda}: |{\lambda}|>1+{\sigma}\}$. To prove that $V\subseteq O_c$ it is sufficient by the first part of this proof to find a single point ${\lambda}\in V\cap O_c$. The fact that $\tau$ is a polynomial with degree $p$ implies that $|\tau({\lambda})|\to\infty$ as $|{\lambda}|\to\infty$. This implies that the solutions of $z^2-\tau({\lambda})z+{\gamma}=0$, where ${\gamma}=\pm {\sigma}^p$, are $z\sim \tau({\lambda})$ and $z\sim {\gamma}/\tau({\lambda})$ to leading order for all large enough $|{\lambda}|$. Therefore ${\lambda}\in O_c$ for all such ${\lambda}$.

The proof is completed by proving that $0\in I_c$. For ${\lambda}=0$ one has $T_p=X_pX_{p-1}\ldots X_1$ where each $X_r$ is of the form ${\raisebox{0.25ex}{\scalebox{0.6}{${\left(\begin{array}{cc}0&1\\ \pm {\sigma}&0 \end{array}\right)}$}}}$. If $p=2m$ it follows that $T_p={\raisebox{0.25ex}{\scalebox{0.6}{${\left(\begin{array}{cc}\pm {\sigma}^m&0\\0&\pm {\sigma}^m \end{array}\right)}$}}}$. The fundamental equation must therefore take one of the forms $z^2-2{\sigma}^m z+{\sigma}^{2m}=0$, $z^2+2{\sigma}^m z+{\sigma}^{2m}=0$ or $z^2-{\sigma}^{2m}=0$. In each case both solutions have modulus ${\sigma}^{p/2}<1$. The same holds if $p=2m+1$.

The final statement of the lemma follows from the following observations. There must be a component of ${{\bf C}}\setminus B_c$ that contains $0$ and there must be an unbounded component. The first part of the proof shows that these are distinct, and the extra hypothesis is that there are no other components.

Our next task is to determine the sets $B_c,\, I_c$ and $O_c$ for certain particular periodic sequences.

\[c1\] If $c_n={\sigma}$ for all $n\in{{\bf Z}}$ then ${{\rm Spec}}(A_c)$ is the ellipse $$\begin{aligned}
{{\rm Spec}}(A_c)&=&\left\{ u+iv: \frac{u^2}{(1+{\sigma})^2}+\frac{v^2}{(1-{\sigma})^2}=1\right\}\label{c1Eucl}\\
&=&\left\{ \rho{{\rm e}}^{i\theta}:
\rho=\frac{1-{\sigma}^2}{\sqrt{1+{\sigma}^2-2{\sigma}\cos(2\theta)}}\right\}.\label{c1polar}\end{aligned}$$ Moreover the interior $U$ of the ellipse equals $I_c$ and the exterior $V$ of the ellipse equals $O_c$.

We have $p=1$ and $T_1={\raisebox{0.25ex}{\scalebox{0.6}{${\left(\begin{array}{cc}0&1\\ -{\sigma}&{\lambda}\end{array}\right)}$}}}$, so $\tau({\lambda})={\lambda}$ and ${\gamma}={\sigma}$. Using (\[Phidef\]) we deduce that ${{\rm Spec}}(A_c)$ is given by (\[c1Eucl\]). The proof is completed by using Lemma \[findIcOc\].

\[c2\] If $c_n=-{\sigma}$ for all $n\in{{\bf Z}}$ then ${{\rm Spec}}(A_c)$ is the ellipse $$\begin{aligned}
{{\rm Spec}}(A_c)&=&\left\{ u+iv: \frac{u^2}{(1-{\sigma})^2}+\frac{v^2}{(1+{\sigma})^2}=1\right\}\label{c2Eucl}\\
&=&\left\{ \rho{{\rm e}}^{i\theta}:
\rho=\frac{1-{\sigma}^2}{\sqrt{1+{\sigma}^2+2{\sigma}\cos(2\theta)}}\right\}.\label{c2polar}\end{aligned}$$ Moreover $I_c$ is the interior of the ellipse and $O_c$ is the exterior of the ellipse.

We have $p=1$ and $T_1={\raisebox{0.25ex}{\scalebox{0.6}{${\left(\begin{array}{cc}0&1\\ {\sigma}&{\lambda}\end{array}\right)}$}}}$, so $\tau({\lambda})={\lambda}$ and ${\gamma}=-{\sigma}$. We omit the rest of proof, which is almost identical to that of Lemma \[c1\].

In the following lemma, starting from Lemmas \[c1\] and \[c2\], and making successive applications of Lemma \[lemmaB\], we compute the spectra of a family of periodic sequences, namely the sequences $c^\pm = {\sigma}c^{(n,\pm)}\in {\Omega}_{\sigma}$, defined by [(\[periodic\_sequences\])]{}. By Lemma \[lem\_periodic\], these sequences are periodic of period $\leq 4^n$.

This next lemma applies for $0<{\sigma}<1$. The corresponding result for ${\sigma}=1$ is equations [(\[spec\_cplus\])]{} and [(\[spec\_cminus\])]{} above.

\[lem\_sf\] Suppose $n\in {{\bf Z}}_+$ and $c^+ = {\sigma}c^{(n,+)}$, $c^- = {\sigma}c^{(n,-)}$. Then $$\label{spectral_formula}
{{\rm Spec}}( A_{c^\pm}) = \{\,\rho{{\rm e}}^{{{\rm i}}\theta}: \rho = \rho_n^\pm(\theta,\sigma)\}$$ where $$\rho_0^+(\theta,\sigma) = \frac{1-\sigma^2}{\left(1+\sigma^2 - 2\sigma\cos 2\theta\right)^{1/2}}, \quad \rho_0^-(\theta,\sigma) = \frac{1-\sigma^2}{\left(1+\sigma^2 + 2\sigma\cos 2\theta\right)^{1/2}},$$ and, for $n\in {{\bf N}}$, $$\rho_n^\pm(\theta,\sigma) =\left(\rho_0^\pm(2^n\theta,\sigma^{2^n})\right)^{1/2^n} = \frac{\left(1-\sigma^{2^{n+1}}\right)^{1/2^n}}{\left(1+\sigma^{2^{n+1}} \mp 2\sigma^{2^n}\cos \left(2^{n+1}\theta\right)\right)^{1/2^{n+1}}}.$$ Moreover, $$I_{c^\pm} = \left\{\,\rho {{\rm e}}^{i\theta}: 0\leq \rho < \rho_n^\pm(\theta,\sigma) \right\}$$ and $$O_{c^\pm} = \left\{\,\rho {{\rm e}}^{i\theta}: \rho > \rho_n^\pm(\theta,\sigma) \right\}.$$

Our proof of [(\[spectral\_formula\])]{} is by induction. We note first that [(\[spectral\_formula\])]{} holds for $n=0$ by Lemmas \[c1\] and \[c2\]. Suppose now that [(\[spectral\_formula\])]{} holds for some $n\geq 0$ and all $0<{\sigma}<1$. Then $${{\rm Spec}}(A_{{\sigma}^2 c^{(n,\pm)}}) = \{\rho{{\rm e}}^{{{\rm i}}\theta}: \rho=\rho_n^\pm(\theta,\sigma^2)\} = \left\{\rho{{\rm e}}^{{{\rm i}}\theta}:\rho=\left( \rho_0^\pm(2^n\theta,\sigma^{2^{n+1}})\right)^{1/2^n}\right\}.$$ Further, since ${\sigma}c^{(n+1,\pm)} = {\sigma}\Gamma_+(c^{(n,+)})=\Gamma_{{\sigma},+}(\sigma^2 c^{(n,+)})$, it follows from Lemma \[lemmaB\] that $${{\rm Spec}}(A_{{\sigma}c^{(n+1,\pm)}}) = \left\{\pm \sqrt{\lambda}: \lambda\in {{\rm Spec}}(A_{{\sigma}^2 c^{(n,\pm)}})\right\}.$$ Combining these equations, we see that [(\[spectral\_formula\])]{} holds with $n$ replaced by $n+1$. Thus [(\[spectral\_formula\])]{} follows by induction.

The formulae for $I_{c^\pm}$ and $O_{c^\pm}$ follow from [(\[spectral\_formula\])]{} and Lemma \[findIcOc\].

We remark that $\rho_n^-(\theta,\sigma) =\rho_n^+(\theta\pm\pi/2^{n+1},\sigma)$, so that the spectra of $A_{c^\pm}$ in the above lemma are related by $${{\rm Spec}}(A_{c^{+}}) = {{\rm e}}^{\pm i\pi/2^{n+1}}\, {{\rm Spec}}(A_{c^-}).$$ This is a symmetry which is surprising from an inspection of the sequences $c^\pm$, which need not even have the same period. (For example, as observed in Section \[sec:maps\], $c^+$ has period 4 and $c^-$ period 2 in the case $n=1$.)

In principle, since $c^\pm$ is periodic, [(\[spectral\_formula\])]{} should be computable alternatively from the characterisation of the spectrum for general periodic sequences in Lemma \[BIO\]. As an example of this, for the sequence $c^-={\sigma}c^{(1,-)}$ which has period $2$, with $c^-_n = (-1)^n{\sigma}$, the transfer matrix $T_2$ is given by $$T_2=X_2X_1={\left(\begin{array}{cc}0&1\\ -{\sigma}&{\lambda}\end{array}\right)}{\left(\begin{array}{cc}0&1\\
{\sigma}&{\lambda}\end{array}\right)}={\left(\begin{array}{cc}{\sigma}&{\lambda}\\ {\sigma}{\lambda}&-{\sigma}+{\lambda}^2 \end{array}\right)}.$$ Applying Lemmas \[quadraticbounds\] and \[BIO\] with $\tau={\lambda}^2$ and ${\gamma}=-{\sigma}^2$, we find that ${{\rm Spec}}(A_c)$ is the set of all ${\lambda}=u+iv$ for which $$\frac{(u^2-v^2)^2}{(1-{\sigma}^2)^2}+ \frac{(2uv)^2}{(1+{\sigma}^2)^2}=1.$$ If one puts ${\lambda}=\rho {{\rm e}}^{i\theta}$, then this may be rewritten in the form [(\[spectral\_formula\])]{}.

The main point of the above theory and calculations are to prove and prepare the use of the following result on operators $A_c$ that are paired periodic operators. To state this result let us introduce the notations $$E_{\sigma}=\left\{ x+iy:\frac{x^2}{(1+{\sigma})^2}+
\frac{y^2}{(1-{\sigma})^2}< 1\right\}\label{ell1}$$ and $$E_{-{\sigma}}=\left\{ x+iy:\frac{x^2}{(1-{\sigma})^2}+
\frac{y^2}{(1+{\sigma})^2}<1\right\}\label{ell2},$$ so that $E_{\sigma}$ and $E_{-{\sigma}}$ are the interiors of the ellipses introduced in Lemmas \[c1\] and \[c2\].

The following lemma is analogous to [@EBD1 Theorem 12], proved there for the non-self-adjoint Anderson model.

\[lem\_two\_periods\] Suppose that $c\in {\Omega}_{\sigma}$ is periodic and $\tau\in \{{\sigma},-{\sigma}\}$, and define $c^*\in {\Omega}_{\sigma}$ by $c^*_n = c_n$, for $n\geq 0$, and $c^*_n=\tau$ for $n< 0$. Then $${{\rm Spec}}(A_{c^*}) \supset \overline{I_c}\setminus E_\tau.$$

Since ${{\rm Spec}}(A_{c^*})$ is closed it is enough to show that ${{\rm Spec}}(A_{c*}) \supset I_c\setminus \overline{E_\tau}$. So suppose that $\lambda \in I_c\setminus \overline{E_\tau}$. Then, by Lemmas \[c1\] and \[c2\] and Lemma \[BIO\], since ${\lambda}\not\in \overline{E_\tau}$, it follows that there exists a non-trivial solution $f$ of $A_{c^*}f={\lambda}f$ such that $f_n\to
0$ exponentially as $n\to -\infty$. Since ${\lambda}\in I_c$, again applying Lemma \[BIO\], it follows that this solution $f$ also decays exponentially as $n\to +\infty$. Thus ${\lambda}$ is an eigenvalue of $A_{c^*}$ so ${\lambda}\in {{\rm Spec}}(A_{c^*})$.

First proof of the main theorem {#firstproof}
===============================

This section is devoted to the proof of Theorem \[maintheorem3\], in which we assume that $0<{\sigma}<1$.

\[lemmaA\] We have $${{\rm Spec}}(A_c)\subseteq { [ \hspace*{-0.15em} [ 1-{\sigma}, 1+{\sigma}] \hspace*{-0.15em} ] } \label{ring}$$ and $${{\rm Spec}}(A_c)\subseteq \{ x+iy:|x|+|y|\leq
\sqrt{2(1+{\sigma}^2)}\},\label{numrange}$$ for every choice of $c\in{\Omega}_{\sigma}$.

We regard $V_cR$ as a small perturbation of $L$ in the identity $A_c=V_cR+L$, noted in the proof of Lemma \[square\]. Since $L$ is a unitary operator with spectrum $\{z:|z|=1\}$, we have $${\Vert}(L-zI)^{-1}{\Vert}=\left| 1-|z|\, \right|^{-1}$$ for all $z$ not on the unit circle. The inclusion (\[ring\]) now follows from ${\Vert}V_cR{\Vert}={\sigma}$ by a perturbation argument; see [@LOTS Th. 9.2.13].

The inclusion (\[numrange\]) depends on an estimate of the numerical range of $A_c$. Following [@LOTS Section 9.3], $x+iy\in{{\rm Num}}(A_c)$ if there exists $f\in \ell^2({{\bf Z}})$ such that ${\Vert}f{\Vert}=1$ and $x+iy=\langle A_c f,f\rangle$. This implies that $$x=\frac{1}{2}\langle (A_c+A_c^\ast)f,f\rangle, \hspace{2em} y=-\frac{i}{2}\langle (A_c-A_c^\ast)f,f\rangle.$$ Therefore $$x+y=\frac{1}{2}\langle Bf,f\rangle$$ where $$B=(A_c+A_c^\ast)-i(A_c-A_c^\ast).$$ A simple calculation shows that $B_{m,n}=0$ unless $|m-n|=1$, while $$B_{n,n+1}=\overline{ B_{n+1,n}}=(1\pm {\sigma})-i(1\mp {\sigma}).$$ Therefore $|B_{n+1,n}|=|B_{n,n+1}|=\sqrt{2(1+{\sigma}^2)}$ for all $n\in{{\bf Z}}$ and $$x+y \leq \frac{1}{2}{\Vert}B{\Vert}\leq \sqrt{2(1+{\sigma}^2)}.$$ The other three steps in the proof of the bound for $|x|+|y|$ are similar.

The statement of our main theorem refers to the open set $$H_{\sigma}=E_{\sigma}\cap E_{-{\sigma}},\label{Hsigma}$$ the intersection of the ellipses $E_{\sigma}$ and $E_{-{\sigma}}$. This set satisfies $${ [ \hspace*{-0.15em} [  0,1-{\sigma}] \hspace*{-0.15em} ] } \subseteq \overline{H_{\sigma}}\subseteq { [ \hspace*{-0.15em} [ 0,r_{{\sigma}} ] \hspace*{-0.15em} ] }
\label{Hsigsize}$$ where $$r_{{\sigma}}=\frac{  1-{\sigma}^{2}  }{  \sqrt{1+{\sigma}^{2}\,}  }.\label{rndef}$$

\[maintheorem3\] If $0<{\sigma}<1$ then $$\{ {\lambda}:|{\lambda}|\leq 1\}\backslash H_{\sigma}\subseteq S_{\sigma}.$$

Note first that if $c^\pm$ and $\rho_n^\pm(\theta,{\sigma})$ are defined as in Lemma \[lem\_sf\], then $$\rho_n^\pm(\theta, {\sigma}) \geq \rho_{{\sigma},n} = \left(\frac{1-{\sigma}^{2^{n+1}}}{1+{\sigma}^{2^n}}\right)^{1/2^n},$$ for all $\theta\in {{\bf R}}$, so that $I_{c^\pm} \supset  \{{\lambda}:|{\lambda}|< \rho_{{\sigma},n}\}$. Thus, defining $c^*\in {\Omega}_{\sigma}$ as in Lemma \[lem\_two\_periods\], with $c=c^+$ or $c^-$ and $\tau=\pm{\sigma}$, we see from Lemma \[lem\_two\_periods\] that $$\label{spectral_inc}
{{\rm Spec}}(A_{c^*}) \supset \overline{I_{c}}\setminus E_\tau \supset \{{\lambda}:|{\lambda}| \leq \rho_{{\sigma},n}\}\setminus E_\tau.$$ Applying Proposition \[quasiergodic\], it follows that, for all $n\in {{\bf N}}$, $$S_{\sigma}\supset \{{\lambda}:|{\lambda}| \leq \rho_{{\sigma},n}\}\setminus H_\tau.$$ The theorem follows since $\sup_{n} \rho_{{\sigma},n} = 1$ and $S_{\sigma}$ is closed.

Lemma \[lemmaA\] and Theorem \[maintheorem3\] together establish that there is a hole in $S_{\sigma}$ which is at least as big as $\{{\lambda}:|{\lambda}|<1-{\sigma}\}$ and which is no larger than $H_{\sigma}$. The numerical computations we have been able to carry out are consistent with a hypothesis that the hole is precisely the set $H_{\sigma}$, i.e. they are consistent with a hypothesis that ${{\rm Spec}}(A_c)\cap
H_{\sigma}=\emptyset$ for every $c\in {\Omega}_{\sigma}$, and hence for every $c\in{{\cal E}}_{\sigma}$.

It should be pointed out, however, that these numerical computations are only for instances where $c$ is periodic, for which we have a characterisation of the spectrum in Lemma \[BIO\]. Thus, strictly speaking, our calculations are evidence of the possibly weaker result that $\pi_{\infty,{\sigma}} \cap H_{\sigma}= \emptyset$; they become evidence that ${{\rm Spec}}(A_c)\cap
H_{\sigma}=\emptyset$ with a hypothesis that $\pi_{\infty,{\sigma}}$ is dense in the part of $S_{\sigma}$ that is contained in the unit disc. This latter statement may or may not be true for ${\sigma}\in (0,1)$, but we have shown in Theorem \[denseness\] that it is true for ${\sigma}=1$.

As an example of the numerical computations we have carried out, the right hand side of Figure \[fig:30pics1\] shows the union of ${{\rm Spec}}(A_c)$ over all periodic $c\in {\Omega}_{\sigma}$ for which the period $N\leq 12$. It is clear from this figure that $\pi_{12,{\sigma}}\cap H_{\sigma}= \emptyset$ for ${\sigma}=0.5$. We note that, rather than using the characterisation in Lemma \[BIO\], we use for these computations the standard Bloch-decomposition formula (e.g. [@LOTS]) that $$\label{spectrumperiodic}
{{\rm Spec}}(A_c) = \bigcup_{|\alpha|=1} {{\rm Spec}}(A^{(N,\mathrm{per})}_{c,\alpha}),$$ where $A^{(N,\mathrm{per})}_{c,\alpha}$ is the $N\times N$ matrix defined in [(\[finitematrix2\])]{} below.

It is not feasible to calculate $\pi_{N,{\sigma}}$, the union of all $2^{N-1}$ periodic spectra of period $N$, for very much larger values of $N$. In Figure \[Hsigplot\] we sample $\pi_{100,{\sigma}}$, for ${\sigma}=0.5$, plotting the union of the spectra of $10^5$ randomly chosen $N\times N$ matrices $A_{c,\alpha}^{(N,\mathrm{per})}$. By randomly chosen we mean here that, in each realisation, $N\in \{1,...,100\}$ is randomly chosen, with higher probabilities for the smaller matrix sizes, and then the vector $c=(c_1,...,c_N)$ is randomly chosen, with each $c_n=\pm {\sigma}$ independent and identically distributed with $\mathrm{Pr}(c_n={\sigma})=0.5$, and finally the phase factor $\alpha$ is randomly chosen from a uniform measure on the unit circle. We see in the figure that clearly, as they have to, the spectra are constrained to lie in the inclusion sets shown in Lemma \[lemmaA\]. We also note that all the spectra lie outside $H_{\sigma}$.

Second proof of the main theorem {#secondproofsection}
================================

In Theorem \[maintheorem6\] of this section we provide a second proof that $$\{{\lambda}:|{\lambda}|\leq 1\}\backslash H_{\sigma}\subseteq
S_{\sigma}\label{secondversion}$$ for all ${\sigma}\in (0,1)$. This proof has a lot in common with the previous one, but it reveals more about the asymptotic behaviour of the solutions of the second order recurrence relation for certain choices of $c\in{\Omega}_{\sigma}$. A key role in this section is played by the sequence $c_e\in {\Omega}_{\sigma}$ defined in Section \[sec:maps\], which sequence was central to the proof of Theorem \[maintheorem\] that appears in [@CCL] (see Theorem \[CCLprop3\] above for more details).

We start with some calculations that do not depend on ${\sigma}$. Throughout this section $\widetilde{c}_n \in \{ \pm 1\}$ is defined for all $n\geq 1$ by the rules $\widetilde{c}_1=1$, $\widetilde{c}_{2n}=\widetilde{c}_{2n-1}\widetilde{c}_n$ and $\widetilde{c}_{2n}+\widetilde{c}_{2n+1}=0$. (In other words, $\widetilde{c}_n=c_{e,n}$, for $n\geq 1$.) The first few values are shown in Table \[tabledata2\]. We will obtain a bound on a transfer matrix $T_{m,{\lambda}}$ associated with this sequence and use this bound to prove Theorem \[maintheorem6\].

Let $u:{{\bf Z}}_+\to{{\bf C}}$ be the solution of $u_{n+1}={\lambda}u_n-\widetilde{c}_n
u_{n-1}$ such that $u_0=0$ and $u_1=1$, so that $u$ is the restriction to ${{\bf Z}}_+$ of the bi-infinite sequence $u_e$ already studied in [@CCL] and discussed in Section \[sec:maps\]. We have observed already in Proposition \[CCLprop\] that $u_n$ is a polynomial of degree $n-1$ in ${\lambda}$ with integer coefficients for all $n\geq 2$. Similarly, if $v:{{\bf Z}}_+\to{{\bf C}}$ is the solution of $v_{n+1}={\lambda}v_n-\widetilde{c}_n v_{n-1}$ such that $v_0=1$ and $v_1=0$, it is easy to see that $v_n$ is a polynomial of degree $n-2$ with integer coefficients for all $n\geq 2$.

$$\begin{array}{rrrr}
n  &  \widetilde{c}_n       & u_n    & v_n   \\
\hline
1&\hspace{2em}1&1& \,\,\,\,0 \\
2&1&{\lambda}& -1 \\
3&-1&{\lambda}^2-1& -{\lambda}\\
4&-1&{\lambda}^3& -{\lambda}^2-1\\
5&1&{\lambda}^4+{\lambda}^2-1&-{\lambda}^3 -2{\lambda}\\
6&-1&{\lambda}^5-{\lambda}&  -{\lambda}^4-{\lambda}^2 +1\\
7&1&{\lambda}^6+{\lambda}^4-1& -{\lambda}^5 -2{\lambda}^3 -{\lambda}\\
8&-1&{\lambda}^7& -{\lambda}^6 -{\lambda}^4 -1\\
9&1&\hspace{2em}{\lambda}^8+{\lambda}^6+{\lambda}^4-1&\hspace{2em}-{\lambda}^7-2
{\lambda}^5-2{\lambda}^3-2{\lambda}\end{array}$$

One may check the computations of $u_m$ and $v_m$ in Table \[tabledata2\] by confirming the determinantal identity $u_mv_{m+1}-v_mu_{m+1}=\pm 1$ for all $m\geq
1$, the left hand side being a polynomial in ${\lambda}$. Here we are referring to a determinantal identity for the transfer matrix $T_{m,{\lambda}}$, defined by $$T_{m,{\lambda}}={\left(\begin{array}{cc} v_{m}&u_{m}\\ v_{m+1}&u_{m+1} \end{array}\right)},$$ which transfers the data of any solution of $x_{n+1}={\lambda}x_n-\widetilde{c}_n x_{n-1}$ from $\{ 0,1 \}$ to $\{ m,m +1 \}$ in the sense that $$T_{m,{\lambda}}{\left(\begin{array}{c}x_0\\ x_1 \end{array}\right)}={\left(\begin{array}{c} x_m\\x_{m+1} \end{array}\right)}.$$ It is easy to verify (see Lemma \[BIO\] above) that $$T_{m,{\lambda}}=X_mX_{m-1}\ldots X_1\label{TSprod}$$ where $$X_r={\left(\begin{array}{cc}0&1\\ -\widetilde{c}_r&{\lambda}\end{array}\right)}\label{Sdetvalue}$$ has determinant $\widetilde{c}_r\in \{\pm 1\}$ for every $r\geq 1$.

The proof of Theorem \[maintheorem6\] we will give below was motivated by numerical evidence that $${{\rm tr}}(T_{2^r,{\lambda}}) ={\lambda}^{2^r}-2$$ holds for all $r\geq 1$ and all ${\lambda}\in{{\bf C}}$; see Table \[tabledata3\]. We prove this crucial identity in Lemma \[Ttau2\].

$$\begin{array}{rr}
n  &  \hspace{2em}{{\rm tr}}(T_{n,{\lambda}})= u_{n+1}+ v_n \\
\hline
1&{\lambda}\\
2&{\lambda}^2-2\\
3& {\lambda}^3-{\lambda}\\
4&{\lambda}^4-2\\
5&{\lambda}^5-{\lambda}^3-3{\lambda}\\
6&{\lambda}^6-{\lambda}^2\\
7& {\lambda}^7-{\lambda}^5-2{\lambda}^3-{\lambda}\\
8&{\lambda}^8-2
\end{array}$$

\[Tdet1\] Let $T$ be a $2\times 2$ matrix with determinant ${\delta}$ and trace $\tau$. If $\tau^2\not= 4{\delta}$ and ${\gamma}$ is the absolute value of the larger root of $z^2-\tau z+{\delta}=0$ then there exists a constant $b$ such that $${\Vert}T^r{\Vert}\leq b\,{\gamma}^r$$ for all $r\geq 1$. If $\tau^2 = 4{\delta}$ then for every ${\varepsilon}>0$ there exists a constant $b_{\varepsilon}$ such that $${\Vert}T^r{\Vert}\leq b_{\varepsilon}({\gamma}+{\varepsilon})^r\label{jordan}$$ for all $r\geq 1$.

The eigenvalues $z_\pm$ of $T$ are the roots $z$ of $z^2-\tau
z+{\delta}=0$. The condition $\tau^2\not= 4{\delta}$ implies that the eigenvalues are distinct, so $T$ is diagonalizable – there exists an invertible matrix $B$ such that $$T=B{\left(\begin{array}{cc} z_+&0\\0&z_- \end{array}\right)} B^{-1}.$$ Therefore $$\begin{aligned}
{\Vert}T^r{\Vert}={\Vert}B{\left(\begin{array}{cc} z_+^r&0\\0&z_-^r \end{array}\right)} B^{-1}{\Vert}\leq  {\Vert}B{\Vert}\, {\Vert}B^{-1}{\Vert}{\gamma}^r.\end{aligned}$$ The slightly worse bound (\[jordan\]) is obtained when $\tau^2=
4{\delta}$ because one has to use the Jordan canonical form for $T$.

\[Tdet3\] The identity $\det(T_{2^n,{\lambda}}) =1$ holds for all $n\geq 1$ and all ${\lambda}\in{{\bf C}}$.

If $m\in{{\bf N}}$ then (\[TSprod\]) and (\[Sdetvalue\]) imply $$\begin{aligned}
\det(T_{2m,{\lambda}})&=& \prod_{r=1}^m \det(X_{2r}X_{2r-1})\\
&=&\prod_{r=1}^m (\widetilde{c}_{2r}\widetilde{c}_{2r-1})\\
&=&\prod_{r=1}^m \widetilde{c}_{r}\\
&=& \det(T_{m,{\lambda}}).\end{aligned}$$ It follows by induction that $$\det(T_{2^n,{\lambda}})=\det(T_{1,{\lambda}})=\widetilde{c}_1=1.$$

The following lemma depends on Proposition \[CCLprop\] above, abstracted from [@CCL], which notes properties of the integer coefficients $p_{i,j}$ of the polynomials $$u_i=\sum_{j=1}^i p_{i,j}{\lambda}^{j-1}.$$

\[Ttau1\] The polynomial $u_m$ is even for odd $m$ and odd for even $m$. Its leading term is ${\lambda}^{m-1}$. If $m=2^n$ and $n\geq 2$ then $$\begin{aligned}
u_m&=& {\lambda}^{m-1},\label{ufortau1}\\
u_{m+1}&=&-1+{\lambda}^{m/2}\sum_{r=0}^{m/4} {\alpha}_r
{\lambda}^{2r}\label{ufortau2}\end{aligned}$$ where ${\alpha}_r\in \{0,1,-1\}$ for all $r$.

The statements in the first two sentences may be proved by induction, using the definition of $u_m$. We prove (\[ufortau1\]) and (\[ufortau2\]) for $m=2^n$ by induction in $n$, noting that both hold for $n\leq 3$; see Table \[tabledata2\]. As in Proposition \[CCLprop\], let $Y$ denote the set of $(i,j)\in {{\bf N}}^2$ such that $p_{i,j}\not= 0$.

To prove (\[ufortau1\]) suppose that $(2^{n+1},j)\in Y$. Proposition \[CCLprop\] implies that $j$ is even and that $(2^n,j/2)\in Y$. The inductive hypothesis now implies that $j/2=2^n$, so $j=2^{n+1}$.

To prove (\[ufortau2\]) suppose that $(2^{n+1}+1,j)\in Y$. Proposition \[CCLprop\] implies that $j$ is odd and either $(2^{n},(j+1)/2)\in Y$ or $(2^{n}+1,(j+1)/2)\in Y$. In the first case we have already proved that $(j+1)/2=2^n$, so $j=2^{n+1}-1$. In the second case the inductive hypothesis implies that $(j+1)/2  \geq
2^{n-1}+1$, so $j\geq 2^{n}+1$ or $(j+1)/2=1$, so $j=1$.

We finally have to evaluate the constant coefficient ${\gamma}_m$ of $u_m$ when $m=2^n+1$. This may be done by considering the defining recurrence relation in the case ${\lambda}=0$, namely ${\gamma}_{r+1}=-\widetilde{c}_r{\gamma}_{r-1}$ subject to ${\gamma}_0=0$ and ${\gamma}_1=1$. This implies that $${\gamma}_{2m+1}=\prod_{r=1}^m \widetilde{c}_{2r}$$ for all $m\in{{\bf N}}$. Therefore ${\gamma}_5={\gamma}_3=-1$ and $$\begin{aligned}
{\gamma}_{8m+1}&=&\prod_{r=1}^m\left(\widetilde{c}_{8r}\widetilde{c}_{8r-2}\widetilde{c}_{8r-4}\widetilde{c}_{8r-6}\right)\\
&=&\prod_{r=1}^m\left(\widetilde{c}_{4r}\widetilde{c}_{8r-1}\widetilde{c}_{8r-2}\widetilde{c}_{4r-2}\widetilde{c}_{8r-5}\widetilde{c}_{8r-6}\right)\\
&=&\prod_{r=1}^m\left(\widetilde{c}_{4r}\widetilde{c}_{4r-2}\right)\\
&=& {\gamma}_{4m+1}\end{aligned}$$ for all $m\in{{\bf N}}$. A simple induction now implies that ${\gamma}_{m}=-1$ for $m=2^n+1$ and all $n\geq 1$.

\[Ttau2\] If $m=2^n$ and $n\geq 2$ then $$\tau={{\rm tr}}(T_{m,{\lambda}})=v_m+u_{m+1}={\lambda}^m-2\label{tauformula}$$ for all ${\lambda}\in{{\bf C}}$.

The proof uses the identity $v_mu_{m+1}-u_mv_{m+1}=1$ of Lemma \[Tdet3\] together with the two identities proved in Lemma \[Ttau1\]. These are identities within the commutative ring ${{\bf Z}}({\lambda})$ of all polynomials with integer coefficents in the indeterminate quantity ${\lambda}$, but they imply similar identities in the commutative ring ${{\bf Z}}(\widehat{{\lambda}})$ of all polynomials with integer coefficients in an indeterminate quantity $\widehat{{\lambda}}$ that satisfies the identity $\widehat{{\lambda}}^{m-1}=0$. (Equivalently one may start by disregarding all terms in the identities that involve ${\lambda}^r$ with $r\geq m-1$.) The identities then simplify to $$\widehat{u}_{m+1} = -1+p,\hspace{2em}
\widehat{v}_{m}\widehat{u}_{m+1}= 1,$$ where $$p(\widehat{{\lambda}})=\widehat{{\lambda}}^{m/2}\sum_{r=0}^{m/4} {\alpha}_r
\widehat{{\lambda}}^{2r}$$ satisfies $p^{2}=0$ in ${{\bf Z}}(\widehat{{\lambda}})$. The second equation can be solved for $\widehat{v}_m$, yielding $$\widehat{v}_{m}=-1-p$$ and hence $\widehat{\tau}=-2$. Returning to the original variable ${\lambda}$ one deduces that $$\tau=-2+\sum_{r\geq m-1} {\beta}_r {\lambda}^r.$$ But (cf. Lemma \[Ttau1\]) it is easily shown that $v_n$ is an even polynomial of degree $n-2$ for odd $n$. Thus, and by Lemma \[Ttau1\], $\tau =v_m+u_{m+1}$ is an even polynomial of degree $m$ with leading coefficient $1$, so $\tau={\lambda}^m-2$.

\[Tdet2\] Following the assumptions and notation of Lemma \[Tdet1\], suppose that ${\delta}=1$ and that there exist $m\in{{\bf Z}}_+$ and $\mu\in{{\bf C}}$ such that $\tau=\mu^m-2$. Then there exists a constant $b$ such that $${\Vert}T^r{\Vert}\leq b\, 4^r \max(|\mu|^{rm},1)$$ for all $r\geq 1$.

\
**Case 1.** If $|\mu|\leq 1$ it suffices to obtain bounds on the solutions $z_\pm$ of $z^2-\tau z+1=0$ when $|\tau|\leq 3$. The solutions satisfy $$|z_\pm|= \left| \frac{\tau}{2}\pm \sqrt{\frac{\tau^2}{4} -1}\right|
\leq\frac{3}{2}+\frac{\sqrt{13}}{2} <4.$$ Lemma \[Tdet1\] now implies that ${\Vert}T^r{\Vert}\leq b \, 4^r$ for all $r\geq 1$.

**Case 2.** If $|\mu|> 1$ it suffices to obtain bounds on the solutions $z_\pm$ of $z^2-\tau z+1=0$ when $|\tau|\leq 3|\mu|^m$. The solutions satisfy $$|z_\pm|= \left| \frac{\tau}{2}\pm \sqrt{\frac{\tau^2}{4} -1}\right|
<4|\mu|^m.$$ Lemma \[Tdet1\] now implies that ${\Vert}T^r{\Vert}\leq b \,
4^r|\mu|^{rm}$ for all $r\geq 1$.

\[fillin\] Let $X_n$, $n\in{{\bf Z}}$, be a periodic sequence of $2\times 2$ matrices with period $m$ and let $T_r=X_rX_{r-1}\ldots X_1$ for all $r\geq
1$. If there exist constants $b_0,\, {\gamma}$ such that ${\Vert}(T_{m})^s{\Vert}\leq b_0 {\gamma}^{s}$ for all $s\geq 0$, then there exists a constant $b_2$ such that ${\Vert}T_r{\Vert}\leq b_2
{\gamma}^{r/m}$ for all $r\geq 1$.

Every $r\in{{\bf Z}}_+$ may be written in the form $r=sm+v$ where $s\geq 0$ and $0\leq v<m$. Using the identity $T_{sm}=(T_m)^s$, one obtains $$\begin{aligned}
{\Vert}T_r{\Vert}&=& {\Vert}X_rX_{r-1}\ldots X_{sm+1}T_{sm}{\Vert}\\
&=& {\Vert}X_vX_{v-1}\ldots X_1(T_{m})^s{\Vert}\\
&\leq & {\Vert}X_vX_{v-1}\ldots X_1{\Vert}b_0{\gamma}^{sm}\\
&\leq & b_0b_1 {\gamma}^{s}\\
&\leq & b_2 {\gamma}^{r/m},\end{aligned}$$ where $b_2=b_0b_1$ and $$b_1=\max_{0\leq v\leq m-1}\{  {\Vert}X_vX_{v-1}\ldots X_1{\Vert}\}.$$

\[maintheorem6\] One has $$\{{\lambda}:|{\lambda}|\leq 1\}\backslash H_{\sigma}\subseteq
S_{\sigma}\label{strongform}$$ for all ${\sigma}\in (0,1)$.

Given ${\sigma}\in (0,1)$ we put $m=2^d$ where $d\in {{\bf N}}$ is large enough to yield $${\sigma}^{1/2} < h=4^{-1/m}.\label{criticalmbound}$$ We use the identities $${\delta}=\det(T_{m,\mu})=1$$ and $$\tau={{\rm tr}}(T_{m,\mu})=\mu^{m}-2$$ proved in Lemmas \[Tdet3\] and \[Ttau2\] and valid for all $\mu\in{{\bf C}}$. Let $c\in{\Omega}_{\sigma}$ be the periodic sequence with period $m$ such that $c_n={\sigma}\widetilde{c}_n$ for all $1\leq n\leq m$. The main task is to prove that if $|{\lambda}|<h$ then all solutions $\xi:{{\bf Z}}\to{{\bf C}}$ of $$\xi_{n+1}={\lambda}\xi_n-c_n\xi_{n-1}\label{xiiterate}$$ decay exponentially as $n\to+\infty$. This will imply, by Lemma \[BIO\], and using the notations of that lemma, that $$I_c \supset \{{\lambda}:|{\lambda}| < h\}.$$ Arguing as in the proof of Theorem \[maintheorem3\], it will then follow from Lemma \[lem\_two\_periods\] and Proposition \[quasiergodic\] that $$S_{\sigma}\supset \{{\lambda}:|{\lambda}| \leq h\} \setminus H_{\sigma},$$ this holding for any $h=4^{-1/m}$ such that [(\[criticalmbound\])]{} holds and $m=2^d$, so that $$S_{\sigma}\supset \{{\lambda}:|{\lambda}| < 1\} \setminus H_{\sigma}.$$ Since $S_{\sigma}$ is closed, [(\[strongform\])]{} will follow.

Thus it remains only to show that all solutions of [(\[xiiterate\])]{} decay exponentially at $+\infty$. To see that this holds, define $x_n={\sigma}^{-n/2}\xi_n$ and $\mu={\sigma}^{-1/2}{\lambda}$ so that (\[xiiterate\]) may be rewritten in the form $$x_{n+1}=\mu x_n-\widetilde{c}_nx_{n-1}$$ for $1\leq n\leq m$. Where $\theta=\max(1,|\mu|)$, Lemma \[Tdet2\] now yields $${\Vert}(T_{m,\mu})^r{\Vert}\leq b\, 4^r\theta^{rm}$$ for all $r\in {{\bf N}}$. Lemma \[fillin\] with ${\gamma}=4\theta^m$ implies $${\Vert}T_{r,\mu}{\Vert}\leq b\, 4^{r/m}\theta^r,$$ and hence $$|x_r|\leq b_3\, 4^{r/m}\theta^r,$$ again for all $r\in{{\bf N}}$. Hence, where $\phi = \max({\sigma}^{1/2},|{\lambda}|)$, $$|\xi_r|\leq b_3\, 4^{r/m}\theta^r{\sigma}^{r/2}=b_3 \left(
\phi h^{-1}\right)^r$$ for all $r\in {{\bf N}}$. Since $0<\phi< h$, it follows that $\xi$ decays exponentially.

Semi-infinite and finite matrices
=================================

All our results so far have focused on calculations of the spectrum of the bi-infinite matrix $A_c$. In this final section we say something about the spectrum of the semi-infinite matrix $$A^+_c= \left(\begin{array}{cccc}
0&1&&\\
c_1&0&1&\\
& c_{2}&0&\ddots\\
&&\ddots&\ddots
\end{array}\right)$$ in the case that $c=(c_1,c_2,...)\in \{\pm \sigma\}^{{\bf N}}$ is pseudo-ergodic (contains every finite sequence of $\pm \sigma$’s as a consecutive sequence). We also say something (though have mainly unanswered questions) about the finite $N\times N$ matrices $$\begin{aligned}
A^{(N)}_c&=& \left(\begin{array}{ccccc}
0&1&&\\
c_1&0&1&\\
&c_{2}&0&\ddots\\
&&\ddots&\ddots& 1\\
&&& c_{N-1} & 0
\end{array}\right)\end{aligned}$$ and $$\begin{aligned}
A^{(N,\mathrm{per})}_{c,\alpha}&=& \left(\begin{array}{ccccc}
0&1&&& \alpha c_N\\
c_1&0&1&\\
&c_{2}&0&\ddots\\
&&\ddots&\ddots& 1\\
\alpha^{-1} &&& c_{N-1} & 0
\end{array}\right).\label{finitematrix2}\end{aligned}$$ Here $A^{(N)}_c$ is tridiagonal, $A^{(N,\mathrm{per})}_c$ is tridiagonal except for “periodising” entries in row $1$ column $N$ and row $N$ column $1$ (in these entries we assume that $|\alpha|=1$), and each $c_j = \pm {\sigma}$: we have in mind particularly the random case where the $c_j$’s are independent and identically distributed random variables taking the values $\pm \sigma$.

Our main result on the spectrum of $A_c$, proved in the previous sections, is that it contains the set $\{\lambda:|\lambda| \leq 1\}\setminus H_\sigma$. We suspect that $H_\sigma$ is a genuine hole in the spectrum for $0<\sigma<1$, i.e. that $H_\sigma\cap S_\sigma = \emptyset$. We have not shown this result but have shown in Lemma \[lemmaA\] the weaker result that $\{\lambda:|\lambda|< 1-\sigma\}\cap S_\sigma = \emptyset$. Our first result in this section is that this hole is not present in the spectrum of the semi-infinite matrix. The proof depends on recent results on semi-infinite pseudo-ergodic operators due to Lindner and Roch [@LR10], derived using characterisations of the index of Fredholm operators, whose matrix representations are banded semi-infinite matrices, in terms of so-called “plus indices” of limit operators, these characterisations derived using $K$-theory results for $C^*$-algebras in [@RRJ].

\[thm:specsemi\] Suppose $c\in \{\pm \sigma\}^{{{\bf N}}}$ is pseudo-ergodic. If $\sigma=1$ then ${{\rm Spec}}(A_c^+) = S$. For all $\sigma\in (0,1]$, $\{\lambda:|\lambda|\leq 1\}\subset {{\rm Spec}}( A_c^+)$.

In the case that $\sigma=1$ it is shown in [@CCL2] that ${{\rm Spec}}(A_c^+)=S$. Thus, for $\sigma=1$, $$\{\lambda:|\lambda|\leq 1\}\subset S= {{\rm Spec}}(A_c^+)$$ follows from Theorem \[maintheorem\] (or [@CCL Theorem 2.3]). For all $\sigma\in (0,1]$ it follows from [@LR10 Theorem 2.1] that the essential spectrum of $A_c^+$, i.e. the set of $\lambda\in{{\bf C}}$ for which $A_c^+-\lambda I^+$ is not Fredholm (here $I^+$ is the identity operator on $\ell^2({{\bf N}})$), is the set $S_\sigma$. Thus and by Theorem \[maintheorem3\], $$(\{\lambda:|\lambda| \leq 1\}\setminus H_\sigma)\subset S_\sigma \subset {{\rm Spec}}(A_c^+).$$ It remains to show that $H_\sigma\subset {{\rm Spec}}(A_c^+)$. But, applying [@LR10 Theorem 2.4] (note that the set $E_-(U,W)$ in the notation of [@LR10 Theorem 2.4] is precisely the set $H_\sigma$ for this operator), it follows that, for $\lambda \in H_\sigma$, either $A_c^+-\lambda I^+$ is not Fredholm or $A_c^+-\lambda I^+$ is Fredholm with index 1: in either of these cases $\lambda\in {{\rm Spec}}(A_c^+)$.

Our other result in this section is to say something about the spectra (sets of eigenvalues) of the finite matrices $A^{(N)}_c$ and $A^{(N,\mathrm{per})}_{c,\alpha}$. The notations $\pi_{N,{\sigma}}$ and $\pi_{\infty,{\sigma}}$ are as defined in and above equation [(\[eq:piinf\])]{} (and $\pi_N$ and $\pi_\infty$ are our abbreviations for $\sigma=1$).

\[thmfinite\] If $0<{\sigma}\leq 1$, $|\alpha|=1$ and $c\in \{\pm{\sigma}\}^N$, then $${{\rm Spec}}(A^{(N,\mathrm{per})}_{c,\alpha}) \subset \pi_{N,{\sigma}}\subset \pi_{\infty,{\sigma}}\subset S_{\sigma}$$ while $${{\rm Spec}}(A^{(N)}_c)\subset \sqrt{{\sigma}} \pi_{2N+2}\subset \sqrt{{\sigma}} \pi_\infty\subset \sqrt{{\sigma}}S.$$ If $\lambda = x+{{\rm i}}y$ is an eigenvalue of $A^{(N,\mathrm{per})}_{c,\alpha}$ then $1-{\sigma}\leq |\lambda|\leq 1+{\sigma}$ and $|x|+|y|\leq \sqrt{2(1+{\sigma}^2)\,}$, while if $\lambda$ is an eigenvalue of $A^{(N)}_c$ then $|x|+|y|\leq 2\sqrt{{\sigma}}$.

The first of these statements is clear from the definition of $\pi_{N,{\sigma}}$, [(\[spectrumperiodic\])]{}, and Proposition \[quasiergodic\] which gives that $\pi_{\infty,{\sigma}}\subset S_{\sigma}$. The second of these statements is shown for ${\sigma}=1$ in [@CCL2 Theorem 4.1]. The second statement follows for $0<{\sigma}<1$ by the observation that, where $d\in \{\pm 1\}^N$, $c={\sigma}d\in \{\pm {\sigma}\}^N$, and $D_N$ is the diagonal matrix with leading diagonal $(1, {\sigma}^{1/2},{\sigma},...,{\sigma}^{(N-1)/2})$, it holds that $
D_N^{-1} A^{(N)}_c D_N = \sqrt{{\sigma}}\,A^{(N)}_d.
$ The last sentence then follows from Lemma \[lemmaA\].

Note that in the last sentence of the above theorem the condition $|x|+|y|\leq 2\sqrt{{\sigma}}$ implies both that $|\lambda|\leq 1+{\sigma}$ and that $|x|+|y|\leq \sqrt{2(1+{\sigma}^2)\,}$.

In Figure \[fig:rand2000\_09025\] we plot the spectra of $A_c^{(N)}$ and $A^{(N,\mathrm{per})}_{c,\alpha}$ for $N=2000$ and $\alpha=1$ for a typical realisation with the entries $c\in \{\pm {\sigma}\}^N$ randomly chosen with the $c_j$ independently and identically distributed with $\mathrm{Pr}(c_j = {\sigma})=0.5$ and ${\sigma}= 0.9025$ so that $\sqrt{{\sigma}}=0.95$ (the several other realisations we have computed are very close in appearance to these plots). Theorem \[thmfinite\] tells us that ${{\rm Spec}}(A_c^{(N)})\subset 0.95 \pi_\infty \subset 0.95 S$ and that ${{\rm Spec}}(A^{(N,\mathrm{per})}_{c,\alpha})\subset S_{0.9025}$, and that if $\lambda=x+{{\rm i}}y$ is an eigenvalue of $A^{(N)}_c$ then $|x|+|y|\leq 1.9$, while if $\lambda$ is an eigenvalue of $A^{(N,\mathrm{per})}_{c,\alpha}$ then $0.075\leq |\lambda|\leq 1.9025$ and $|x|+|y|\leq \sqrt{2(1+{\sigma}^2)\,}\approx1.905$.

It is clear from Figure \[fig:rand2000\_09025\] that Theorem \[thmfinite\] is only the beginning of the story. We observe in the figure a hole in the spectrum of $A^{(N,\mathrm{per})}_{c,\alpha}$, but it is a hole of radius approximately 0.6, not 0.075, with a large proportion of the eigenvalues positioned on the boundary of this hole, while outside the hole the spectra of $A^{(N,\mathrm{per})}_{c,\alpha}$ and $A^{(N)}_c$ appear near identical. The same qualitative behaviour is visible in Figure \[fig:rand2000\_05\], which is a similar plot except that ${\sigma}$ is reduced to 0.5 and we change the probability distribution, making it twice as likely that the entries of the vector $c$ are $-{\sigma}$ rather than ${\sigma}$. This change of probability distribution introduces an asymmetry, in particular an asymmetry in the hole in the spectrum (if we instead compute with $\mathrm{Pr}(c_j = \sigma)=1/2$ then typical realisations have spectra which are approximately invariant under the dihedral symmetry group $D_2$ of the square). Of course our methods, which are not probabilistic, have nothing to say about such asymmetries, indeed nothing, beyond Theorem \[thmfinite\], to say about the almost sure spectra of $A_c^{(N)}$ or $A^{(N,\mathrm{per})}_{c,\alpha}$ as $N\to\infty$.

[99]{}

A. Böttcher, Infinite matrices and projection methods, pp. 2-74 in “Lectures on Operator Theory and its Applications”, Fields Institute Monographs, ed. Peter Lancaster. Amer. Math. Soc. Publ., Providence, RI, 1995.

A. Böttcher, Y. I. Karlovich, Carleson curves, Muckenhoupt weights, and Toeplitz operators, Basel, Birkhäuser, 1997.

A. Böttcher, B. Silbermann, Introduction to Large Truncated Toeplitz Matrices, New York, Springer-Verlag, 1999.

A. Böttcher, B. Silbermann, Analysis of Toeplitz Operators, 2nd Ed., New York, Springer-Verlag, 2006.

S. N. Chandler-Wilde, R. Chonchaiya and M. Lindner, Eigenvalue problem meets Sierpinski triangle: computing the spectrum of a non-self-adjoint random operator, Oper. Matrices, to appear. Preprint at arXiv:1003.3946v3

S. N. Chandler-Wilde, R. Chonchaiya and M. Lindner, On the spectra and pseudospectra of a class of non-self-adjoint random matrices and operators, submitted for publication, 2011. Preprint at arXiv:1107.0177v1

S. N. Chandler-Wilde and M. Lindner, Limit Operators, Collective Compactness, and the Spectral Theory of Infinite Matrices, Memoirs AMS 210 (2011), No. 989.

G. M. Cicuta, M. Contedini and L. Molinari: Non-Hermitian tridiagonal random matrices and returns to the origin of a random walk, J. Stat. Phys. 98 (2000), 685-699.

E. B. Davies, Spectral properties of random non-self-adjoint matrices and operators, Proc. Roy. Soc. London A 457 (2001) 191-206.

E. B. Davies, Spectral theory of pseudo-ergodic operators, Commun. Math. Phys. 216 (2001) 687-704.

E. B. Davies, Linear Operators and Their Spectra, Camb. Univ. Press, Cambridge, 2007.

E. B. Davies, B. Simon, Scattering theory for systems with different spatial asymptotics on the left and right, Commun. Math. Phys. 63 (1978) 277-301.

J. Feinberg and A. Zee, Non-Hermitean localization and de-localization, Phys. Rev. E 59 (1999), 6433-6443.

J. Feinberg and A. Zee, Spectral curves of non-Hermitean Hamiltonians, Nucl. Phys. B 552 (1999), 599-623.

I. Y. Goldsheid, B. A. Khoruzhenko, Distribution of eigenvalues in non-Hermitian Anderson model, Phys. Rev. Lett. 80 (1998) 2897-2901.

I. Y. Goldsheid, B. A. Khoruzhenko, Thouless formula for random non-Hermitian Jacobi matrices, Israel J. Math. 148 (2005) 331-346.

D. E. Holz, H. Orland and A. Zee, On the remarkable spectrum of a non-Hermitian random matrix model, J. Phys. A, Math. and General, 36 (2003), 3385-3400.

M. Lindner, Infinite Matrices and their Finite Sections: An Introduction to the Limit Operator Method, Birkhäuser, 2006.

M. Lindner and S. Roch, Finite sections of random Jacobi operators, SIAM J. Numer. Anal., to appear. Preprint at arXiv:1011.0907v1

V. S. Rabinovich, S. Roch and J. Roe, Fredholm indices of band-dominated operators, Integral Equations Operator Theory 49 (2004), 221-–238.

V. S. Rabinovich, S. Roch, and B. Silbermann, Limit Operators and Their Applications in Operator Theory, Birkhäuser, 2004.
