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}$$


$$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)$$ enter image description here


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.

  • $\begingroup$ Also: do you mean positive semi definite or entrywise positive semi definite? $\endgroup$ – lcv Oct 24 '18 at 7:46
  • $\begingroup$ @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 $\endgroup$ – Suvrit Oct 24 '18 at 10:11
  • $\begingroup$ @lcv I mean the usual notation of psd-ness. $\endgroup$ – Suvrit Oct 24 '18 at 10:12
  • $\begingroup$ @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. $\endgroup$ – Suvrit Oct 24 '18 at 19:04

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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