7
$\begingroup$

Given an $m\times n$ real matrix $C$.

Let $a_i\in\{-1,1\}$ and $b_i\in\{-1,1\}$. Consider $$q=\left\|\text{diag}(a_1,\ldots,a_m)C + C\text{diag}(b_1,\ldots,b_n)\right\|$$ where the norm is the induced 2-norm $\|m\|=\text{max}_{|x|_2=1}|mx|_2$

The minimum possible value of $q$ is of course $0$, when all $a_i$ are 1 and all $b_i$ are $-1$ (or vice versa). The maximum possible value of $q$ is $2\|C\|$, when all $a_i=b_i=1$.

Question: what is the second smallest value $q$ could have? The answer will depend on $C$. I am looking for a way to calculate this, an algorithm, preferably one that doesn't require trying all $2^{m+n}$ possibilities.

Thoughts and background

The problem is symmetric $a_i\rightarrow-a_i$,$b_i\rightarrow-b_i$ gives the same $q$. Even making use of this, the naive algorithm is still $O(2^{m+n-1})$.

$q$ can be written in terms of the Hadamard product as well: $$q=\|C\circ M\|$$ $$M_{ij}=a_i+b_j$$ The matrices $C$ of interest here are not easily characterizable, but they are always sparse ($O(1)$ nonzero elements per row and per column). The simplest $C$ of practical interest is $$\left( \begin{array}{cccc} 1 & -1 & 0 & 0 \\ -1 & 1 & 0 & 0 \\ 0 & 0 & 1 & -1 \\ 0 & 0 & -1 & 1 \\ 1 & 0 & -1 & 0 \\ 0 & 1 & 0 & -1 \\ -1 & 0 & 1 & 0 \\ 0 & -1 & 0 & 1 \\ \end{array} \right)$$ for which the second-smallest $q$, let us call it $q_2$, is $2$ (I tried all $2^{12}$ possibilities). This is attained when $[a_1,\ldots,a_m]=[-1, 1, -1, 1, 1, -1, 1, -1]$ and $[b_1,\ldots,b_n]=[-1,1,-1,1]$: $$q_2=\left\| \begin{array}{cccc} -2 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 \\ 0 & 0 & -2 & 0 \\ 0 & 0 & 0 & 2 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ \end{array} \right\|=2$$

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.