# Matrix rescaling increases lowest eigenvalue?

Consider the set $$\mathbf{N}:=\left\{1,2,....,N \right\}$$ and let $$\mathbf M:=\left\{ M_i; M_i \subset \mathbf N \text{ such that } \left\lvert M_i \right\rvert=2 \text{ or }\left\lvert M_i \right\rvert=1 \right\}$$ be the set of all subsets of $$\mathbf{N}$$ that are of cardinality $$1$$ or $$2.$$

The cardinality of the set $$\mathbf M$$ itself is $$\binom{n}{1}+\binom{n}{2}=:K$$

We can then study for $$y \in (0,1)$$ the $$K \times K$$ matrix

$$A_N = \left( \frac{\left\lvert M_i \cap M_j \right\rvert}{\left\lvert M_i \right\rvert\left\lvert M_j \right\rvert}y^{-\left\lvert M_i \cap M_j \right\rvert} \right)_{i,j}$$

and

$$B_N = \left( \left\lvert M_i \cap M_j \right\rvert y^{-\left\lvert M_i \cap M_j \right\rvert} \right)_{i,j}.$$

Question I conjecture that $$\lambda_{\text{min}}(A_N)\le \lambda_{\text{min}}(B_N)$$ for any $$N$$ and would like to know if one can actually show this?

As a first step, I would like to know if one can show that $$\lambda_{\text{min}}(A_N)\le C\lambda_{\text{min}}(B_N)$$ for some $$C$$ independent of $$N$$?

In fact, I am not claiming that $$A_N \le B_N$$ in the sense of matrices. But it seems as if the eigenvalues of $$B_N$$ are shifted up when compared with $$A_N.$$

Numerical evidence:

For $$N=2$$ we can explicitly write down the matrices $$A_2 =\left( \begin{array}{ccc} \frac{1}{y} & 0 & \frac{1}{2 y} \\ 0 & \frac{1}{y} & \frac{1}{2 y} \\ \frac{1}{2 y} & \frac{1}{2 y} & \frac{1}{2 y^2} \\ \end{array} \right) \text{ and }B_2 = \left( \begin{array}{ccc} \frac{1}{y} & 0 & \frac{1}{y} \\ 0 & \frac{1}{y} & \frac{1}{y} \\ \frac{1}{y} & \frac{1}{y} & \frac{2}{y^2} \\ \end{array} \right)$$

We obtain for the lowest eigenvalue of $$A_2$$ (orange) and $$B_2$$(blue) as a function of $$y$$

For $$N=3$$ we get qualitatively the same picture, i.e. the lowest eigenvalue of $$A_3$$ remains below the lowest one of $$B_3$$:

In this case:

$$A_3=\left( \begin{array}{cccccc} \frac{1}{y} & 0 & 0 & \frac{1}{2 y} & 0 & \frac{1}{2 y} \\ 0 & \frac{1}{y} & 0 & \frac{1}{2 y} & \frac{1}{2 y} & 0 \\ 0 & 0 & \frac{1}{y} & 0 & \frac{1}{2 y} & \frac{1}{2 y} \\ \frac{1}{2 y} & \frac{1}{2 y} & 0 & \frac{1}{2 y^2} & \frac{1}{4 y} & \frac{1}{4 y} \\ 0 & \frac{1}{2 y} & \frac{1}{2 y} & \frac{1}{4 y} & \frac{1}{2 y^2} & \frac{1}{4 y} \\ \frac{1}{2 y} & 0 & \frac{1}{2 y} & \frac{1}{4 y} & \frac{1}{4 y} & \frac{1}{2 y^2} \\ \end{array} \right)\text{ and } B_3=\left( \begin{array}{cccccc} \frac{1}{y} & 0 & 0 & \frac{1}{y} & 0 & \frac{1}{y} \\ 0 & \frac{1}{y} & 0 & \frac{1}{y} & \frac{1}{y} & 0 \\ 0 & 0 & \frac{1}{y} & 0 & \frac{1}{y} & \frac{1}{y} \\ \frac{1}{y} & \frac{1}{y} & 0 & \frac{2}{y^2} & \frac{1}{y} & \frac{1}{y} \\ 0 & \frac{1}{y} & \frac{1}{y} & \frac{1}{y} & \frac{2}{y^2} & \frac{1}{y} \\ \frac{1}{y} & 0 & \frac{1}{y} & \frac{1}{y} & \frac{1}{y} & \frac{2}{y^2} \\ \end{array} \right)$$

The matrices are of the form $$A=\begin{pmatrix} 1 & C \\ C^* & D \end{pmatrix}, \quad\quad B= \begin{pmatrix} 1 & 0 \\ 0 & 2 \end{pmatrix} A \begin{pmatrix} 1 & 0\\ 0&2\end{pmatrix} ,$$ with the blocks corresponding to the sizes of the sets $$M_j$$ involved.

Let $$v=(x,y)^t$$ be a normalized eigenvector for the minimum eigenvalue $$\lambda$$ of $$B$$. Then $$(x,2y)A\begin{pmatrix} x \\ 2y \end{pmatrix} = \lambda$$ also, but this modified vector has larger norm.

So the desired inequality $$\lambda_j(A)\le\lambda_j(B)$$ (for all eigenvalues, not just the first one) will follow if we can show that $$B\ge 0$$. This is true for $$y=1$$ because in this case we can interpret $$|M_j\cap M_k|=\sum_n \chi_j(n)\chi_k(n)$$ as the scalar product in $$\ell^2$$ of the characteristic functions, and this makes $$v^*Bv$$ equal to $$\|f\|_2^2\ge 0$$, with $$f=\sum v_j\chi_j$$.

For general $$y>0$$, we have $$B(y)=(1/y)B(1) + D$$, for a diagonal matrix $$D$$ with non-negative entries.

Claim. $$\lambda_\min(A_N) \le 4\lambda_\min(B_N)$$.

Proof. Let $$C_N:=\bigl[\tfrac{1}{|M_i||M_j|}\bigr]$$. Then, $$B_N = A_N \circ C_N$$, where $$\circ$$ denotes the Hadamard product. Observe that by construction both $$A_N$$ and $$C_N$$ are positive semidefinite, so $$B_N$$ is also psd. Let's drop the subscript $$N$$ for brevity. Define $$c = \text{diag}(C)$$ sorted in decreasing order, so in particular, $$c_\min = \min_{1\le i \le N} 1/|M_i|^2=1/4$$.

Now, from Theorem 3(ii) of Bapat and Sunder, it follows that: $$\begin{equation*} \lambda_\min(B)=\lambda_\min(A \circ C) \ge \lambda_\min(A)c_\min = \lambda_\min(A_N)/4. \end{equation*}$$

Note: The result of Bapat and Sunder is more general. For psd matrices $$A$$ and $$C$$ it states that $$\begin{equation*} \prod_{j=k}^n \lambda_j(A\circ C) \ge \prod_{j=k}^n\lambda_j(A)c_j, \end{equation*}$$ where $$1\le k \le n$$, and $$\lambda_1(\cdot)\ge \lambda_2(\cdot) \ge \cdots \ge \lambda_n(\cdot)$$, while $$c$$ is as above.

• Also: do you mean positive semi definite or entrywise positive semi definite? – lcv Oct 24 '18 at 7:46
• @ChristianRemling Well, each entry of $A$ and $C$ can be written as an inner product (as you now also are doing in your answer)....hence the semi-definiteness – Suvrit Oct 24 '18 at 10:11
• @lcv I mean the usual notation of psd-ness. – Suvrit Oct 24 '18 at 10:12
• @ChristianRemling sorry, my bad; somehow I thought that because it is intersection, it's obvious for $A$, and of course $C=zz^T$, so that's also clear. – Suvrit Oct 24 '18 at 19:04