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


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.