Let $A \in \{\pm 1\}^{n \times n}$ be a symmetric matrix whose diagonal entries are $+1$. Let $f(A)$ be the smallest number of signs we need to change in $A$ so that it becomes positive semidefinite (while preserving symmetry). My questions are:

  1. Let $A_n$ be an $n \times n$ matrix with all off-diagonal entries equal to $-1$. What is the value of $f(A_n)$?

  2. Let $f_{\max}(n)$ be the maximum of $f(A)$ over all suitable $n \times n$ matrices. Is $f_{\max}(n) = f(A_n)$ true? What is the value of $f_{\max}(n)$?

I am also interested in the same questions for weighted $f(A)$, where changing any element by $x$ costs us $|x|$, and we want to make $A$ positive semidefinite as cheaply as possible.

  • $\begingroup$ It will be worth checking if $f(A)$ is monotonic. That is, if $g_{i,j}(A)$ is the matrix resulting from switching the signs of $A_{i,j}$ and $A_{j,i}$ so that the smallest eigenvalue of $A$ is (strictly) increased, then does it follow that $f(g_{i,j}(A)) < f(A)$? $\endgroup$ – Josiah Park Nov 3 '18 at 15:47

The answer to part 1 is $\lceil \frac{n^2}{2}\rceil-n$. Any fewer than that and the vector $v$ of all $1$'s will satisfy $v^\top Av< \lfloor\frac{n^2}{2}\rfloor-\lceil \frac{n^2}{2}\rceil\le 0$. Let $w$ be the $n$-by-$1$ vector with $i$ entry $(-1)^i$. Then $w w^\top$ is $\lceil \frac{n^2}{2}\rceil-n$ moves away from $A_n$. It has $n-1$ eigenvalues equal to $0$ and one eigenvalue equal to $n$ corresponding to the eigenvector $w$.

| cite | improve this answer | |

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.