# Making binary matrix positive semidefinite by switching signs

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.

• 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)$? – 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$$.