Let $\|M\|:=\sup_{u:\|u\|=1}\|Mu\|$ be the operator norm induced by the Euclidean distance.

Suppose $A$ is a $k\times k$ symmetric matrix with $A_{ij}>0$ for all $i,j$ and $\sum_{i,j} A_{ij} = 1.$ Let $A_i$ be the sum of all elements in row $i$ (or column $i$) of $A.$ Let $B$ be a matrix with entries $$B_{ij} = \frac{A_{ij}^2}{A_i A_j}~.$$ We may show $\|B\|\in \left[1/k,1\right].$ Let $B^\prime$ be identical to $B$ except that its row $k$ and column $k$ are zeroed out.

I want to show a quantitative version of the following qualitative conjecture:

If $A_i$ is large, say $\sim \Theta\left(1/k\right)$ for all $i$ except $i=k,$ for which $A_k\sim o\left(1/k\right),$ then $\frac{\|B^\prime\|}{\|B\|}$ is very close to 1, and approaches $1$ as $A_k$ approaches zero.

Note that the entry $B_{kk}$ need not be small, although yes, $B_{ik}, B_{ki}$ for $i\neq k$ will be small.

Note also that I am interested in the ratio of the two norms being close to 1, not their difference being close to 0. Since each norm may be individually as small as $\frac 1k,$ it is the ratio that is of interest to me.

Concretely, suppose $$A_i = \begin{cases} \frac{1-\epsilon}{k-1}, & i=1,2,\ldots,k-1~, \\ \epsilon, & i = k~. \end{cases}$$ Can we show $$\frac{\|B^\prime\|}{\|B\|} = 1 + O(\epsilon^2)~?$$

Including here the simple argument for why $\|B\|\in\left[1/k,1\right]:$

Note that $B$ is similar to $C$ where $C_{ij} = \frac{A_{ij}^2}{A_j^2}$ and then observe that $\sum_{j=1}^k C_{ij} \in\left[1/k,1\right]$ for each $i.$ By Perron-Frobenius theory, the spectral radius of $C$ lies in $\left[1/k,1\right]$ and $B$ is symmetric, so its spectral norm equals its spectral radius.


I discovered that my conjecture is incorrect. Here is a simple counterexample.

First, let's allow $A_{ij}=0$ for some $i,j.$ Let

$$A_{ij} = \begin{cases}\frac{1-\epsilon}{(k-1)^2} & 1\leq i,j\leq k-1 \\ \epsilon & i=j=k \\ 0 & \mbox{else}. \end{cases}$$

Then, $\|B\| = 1$ since $B_{kk} = 1,$ and we know that $\|B\|\in[1/k,1].$ However, $\|B^\prime\| = \frac{1}{k-1}.$

To get a counterexample with all $A_{ij}$ strictly positive, let

$$A_{ij} = \begin{cases}\frac{1-\epsilon}{(k-1)^2} & 1\leq i,j\leq k-1 \\ \epsilon-(2k-2)\delta & i=j=k \\ \delta & \mbox{else} \end{cases},$$

and choose $\delta$ much much smaller than $\frac{\epsilon}{k}.$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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