Making binary matrix positive semidefinite by switching signs

Question

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.

Answer 1

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