I am trying to derive the bound of the row sum of a transformed matrix

15 Views Asked by At

We have a symmetric binary matrix $K_n$ with diagonals all 1: $K_n = \left( K_{ij} \right)_{i,j=1}^n$ and apply eigenvalue decomposition to it: $$ {K}_n: = Q_n \Lambda_n Q_n^{\top} = Q_n \max\{ \Lambda_n, 0\} Q_n^{\top} + Q_n \min \{ \Lambda_n, 0\} Q_n^{\top} \equiv {K}_n^+ + {K}_n^{-}, $$ where $\Lambda_n = \text{diag}\{\lambda_1,\ldots, \lambda_n\}$. We assume the eigenvalues are ordered and $\omega$, $\nu$ and $\gamma$ are the numbers (counting multiplicities) of positive, negative and zero eigenvalues of $K_n$ respectively. We can represent the elements in each matrix as \begin{align*} K_{ij}^{+} =& \sum_{k=1}^{\omega} v_{ik}v_{kj}\lambda_k \\ K_{ij}^{-} =& \sum_{k=\nu+\omega+1}^n v_{ik}v_{kj}\lambda_k \\ K_{ij} =& \sum_{k=1}^n v_{ik}v_{kj}\lambda_k = K_{ij}^{+} + K_{ij}^{-} \in \{0,1\} \end{align*} with constraints that $\sum_{k=1}^n \lambda_k = n$, $\sum_{k=1}^n v_{ik}^2 \lambda_k = 1$, $\sum_{k=1}^n v_{ik}^2 = 1$ and $\sum_{k=1}^n v_{ik} v_{kj} = 0$. My goal is to show that $\frac{1}{n}\sum_{i=1}^n\sum_{j=1}^n |K_{ij}^{-}| = o(n^1/2)$ given that $\frac{1}{n}\sum_{i=1}^n\sum_{j=1}^n |K_{ij}^{-}| ~ n^1/3$. I derived a bound but it's too loose: note that \begin{align*} |\lambda_k v_{kj} | = |\sum_{l=1}^n K_{jl} v_{kl}| \le \sqrt{\sum_{l=1}^n K_{jl}^2 \sum_{l=1}^n v_{kl}^2} = \sqrt{ \sum_{l=1}^n K_{jl} } \end{align*} \begin{align*} & \sum_{j=1}^n |K_{ij}^-| = \sum_{j=1}^n \left|\sum_{k^-}^n v_{ik}v_{kj} \lambda_k \right| \\ \le & \sum_{j=1}^n \sum_{k^-}^n \left|v_{ik}\right| \left|v_{kj} \lambda_k \right| = \sum_{k^-}^n \left|v_{ik}\right| \sum_{j=1}^n \left|v_{kj} \lambda_k \right| \\ \le & \sum_{k^-}^n \left|v_{ik}\right| \sum_{j=1}^n \sqrt{ \sum_{l=1}^n K_{jl} } \end{align*} then $$ \frac{1}{n} \sum_{i=1}^n \sum_{j=1}^n |K_{ij}^-| \le \frac{1}{n} \sum_{i=1}^n \sum_{k^-}^n \left|v_{ik}\right| \sum_{j=1}^n \sqrt{ \sum_{l=1}^n K_{jl} } $$