# Bound the eigenvalue of product of matrices?

Let $H$ be a $n \times n$ real symmetric matrix that has eigenvalues with absolute value less than 1. Define the matrix $M = \prod_{i=1}^n (I - e_ie_i^{\top}H)$ where $e_i$ denotes the $i^\text{th}$ canonical basis vector of $\mathbb{R}^n$.

Assuming that $H$ has at least one negative eigenvalue, is it true that $M$ has an eigenvalue with absolute value greater than 1?

• By the product, I guess you mean (1) $i=j$; and (2) the product should be taken in increasing order (as these matrices don't commute). – Anthony Quas Jun 9 '17 at 4:19
• It is funny: I can almost show it. Namely, I can show that there is a vector $x\in \mathbb R^n$ such that $|M^nx|\to\infty$ (that is easy: just take any $x$ with $\langle Hx,x\rangle<0$ and notice that if $y=x-\langle Hx,e\rangle e$ for a unit vector $e$, then $\langle Hy,y\rangle\le \langle Hx,x\rangle-\langle Hx,e\rangle^2$ and we cannot have the scalar products very small throughout the entire cycle). However, I cannot yet exclude the case of a non-trivial Jordan block with an eigenvalue of absolute value $1$ if $H$ is degenerate. Any ideas? – fedja Jun 10 '17 at 1:46

OK, looks like I've got it. Since it is pretty late here now, it would be nice if someone could check that I haven't written some nonsense (I apologize in advance if I have).

Let $N(H)$ be the kernel of $H$, let $Q$ be the orthogonal projector to $N(H)$ and let $P$ be the orthogonal projector to $N(H)^\perp$. Note that since $H$ is real symmetric, we have $QH=HQ=0$ and $PHP=H$.

Now let $e$ be a unit vector and let $X=x-\langle Hx,e\rangle e$. Then $PX=Px-\langle PHP(Px),Pe\rangle Pe$. Thus, if $x_j\in \mathbb R^n$ satisfy the recursion $x_{j+1}=x_j-\langle Hx_j,e_j\rangle e_j$ where $e_j$ cycle through an orthonormal basis in $\mathbb R^n$, then $y_j=Px_j\in P(\mathbb R^n)$ satisfy the recursion $y_{j+1}=y_j-\langle \widetilde H y_j,v_j\rangle v_j$, where $v_j=Pe_j$ cycle through some complete system of vectors whose norms are bounded by $1$. Moreover, if $H$ has a negative eigenvalue, so does $\widetilde H$, but the advantage is that $\widetilde H$ is invertible in $P(\mathbb R^n)$.

Thus, we reduced the problem to the following:

Let $E$ be a real Euclidean space, let $v_j\in E$ be a sequence cycling through a fixed complete system of vectors with norm at most $1$, let $H:E\to E$ be any invertible symmetric linear operator of norm at most $1$, let $x_0\in E$ be any vector with $\langle Hx_0,x_0\rangle<0$. Then the sequence of vectors defined by the recursion $x_{j+1}=x_j-\langle Hx_j,v_j\rangle v_j$ grows at least geometrically in norm.

The key inequality is $$\langle Hx_{j+1},x_{j+1}\rangle = \langle Hx_{j},x_{j}\rangle-\langle Hx_{j},v_{j}\rangle^2(2-\langle Hv_{j},v_{j}\rangle) \\ \le \langle Hx_{j},x_{j}\rangle-\langle Hx_{j},v_{j}\rangle^2\,.$$ Since $H$ is invertible, we have $|HX|\ge c|X|$ for all $X\in E$ with some $c>0$. Now, if $|\langle Hx_j,v_j\rangle|<\delta|x_j|$ throughout the whole cycle with very small $\delta$, then all vectors in the cycle differ from the first vector $X$ in the cycle by at most $O(\delta)|X|$ and we derive that $|\langle HX,v_j\rangle|=O(\delta)|X|$, which, due to the completeness of the system of vectors $v_j$ over which we cycle, results in $|HX|=O(\delta)|X|$, contradicting the lower bound if $\delta>0$ is small enough. Thus, in each cycle we never increase $\langle Hx_j,x_j\rangle$ and have the inequality $$\langle Hx_{j+1},x_{j+1}\rangle \le \langle Hx_j,x_j\rangle-\delta^2|x_j|^2 \\ \le (1+\delta^2)\langle Hx_j,x_j\rangle$$ at least once. That is the desired geometric growth. The end.

• Hello, so you proved that there exists a $x$ so that $\lim_{n \to \infty} |M^n x|$ diverges, but this is not sufficient for $M$ to have an eigenvalue with absolute value greater than $1$, but greater than or equal to one. – user31317 Jun 11 '17 at 8:39
• Or since $H$ is invertible, then you claim $M$ has no eigenvalue with abs value 1? – user31317 Jun 11 '17 at 8:56
• @user31317 I proved now that the norm growth is geometric, not just polynomial, which can be only if there is an eigenvalue bigger than one in absolute value. – fedja Jun 11 '17 at 19:21
• Can you explain in more detail why the geometric growth suffices? Can be proved using Jordan normal form? – user31317 Jun 12 '17 at 4:03
• I think I got it. – user31317 Jun 12 '17 at 6:15