Show that there exists a diagonal matrix $B$ the diagonal entries of which are $±1$ such that $A + B$ is nonsingular. Let $n$ be an odd positive integer let $A ∈ M_{n×n}(\mathbb{R})$. Show that there exists a
diagonal matrix $B$ the diagonal entries of which are $±1$ such that $A + B$ is nonsingular.
Any solutions/hints are greatly appreciated. I'm not sure how to do this.
 A: We can do this by induction on $n$ (and I don't need $n$ to be odd, it works in general). The case $n=1$ is of course trivial. For general $n$, let's now choose the $B_{jj}$, $j\ge 2$, such that the lower right $(n-1)\times (n-1)$ block of $A+B$ is non-singular (possible by the IH).
I claim that now at least one choice of $B_{11}=\pm 1$ works for the whole matrix. Let's write $C=A+B$, with the choices above and $B_{11}=-1$. If my claim is wrong, then
$$
Cv=(C+2P)w=0 , \quad\quad\quad\quad (1)
$$
for certain vectors $v,w\not=0$, and with $P$ being the projection on the first unit vector. Write $v=ce_1+v_2$, $w=de_1+w_2$, with $v_2=(1-P)v$ and similarly for $w_2$.
Then $(1-P)C(cw_2-dv_2)=0$, thus $cw_2=dv_2$ since $(1-P)C(1-P)$ is non-singular on $R(1-P)$. Now we can look at the $e_1$ components of (1), and we find that $cd=0$, so $v=0$ or $w=0$.
It follows that $C$ or $C+2P$ is non-singular.
A: I saw this old question bumped up by the system a few minutes ago, so I try to offer a simpler answer here. We will prove the assertion by mathematical induction. The base case $n=1$ is trivial. For the induction step, partition $A$ as $\pmatrix{\ast&\ast\\ \ast&A'}$, where $A'$ is $(n-1)\times(n-1)$. By induction hypothesis, there exists a $\{-1,1\}$-diagonal matrix $B'$ such that $\det(A'+B')\ne0$. Since the determinant of a matrix is linear in the first row, we get
\begin{align*}
&\det\left(A+\pmatrix{1\\ &B'}\right)-\det\left(A+\pmatrix{-1\\ &B'}\right)\\
&=\det\pmatrix{2&0\\ \ast&A'+B'}=2\det(A'+B')\ne0.
\end{align*}
Hence either $B=\pmatrix{1\\ &B'}$ or $B=\pmatrix{-1\\ &B'}$ will fill the bill.
A: My proof is similar to Christian Remling's, but uses a different argument in the induction stop.
We use induction over $n$. $n = 1$ is obvious. Now, let $n > 1$. We partition the matrix $A$ into blocks of size $1$ and $n-1$. The lower-right $(n-1)\times(n-1)$ is handled by the induction hypothesis. In order to conclude, we have to show that the block matrix
$$\begin{pmatrix}A_{11} \pm 1 & A_{1,2} \\ A_{2,1} & A_{2,2} + B_{2,2}\end{pmatrix}$$
is invertible for one choice of $\pm1$. The $(n-1)\times(n-1)$-block $A_{2,2} + B_{2,2}$ is already invertible. This block matrix is invertible, iff the Schur complement $$A_{1,1} \pm 1 - A_{1,2} \, (A_{2,2} + B_{2,2})^{-1} \, A_{2,1}$$ is invertible. This is a scalar, and thus invertible for one choice of $+1$ or $-1$ (note that this is the assertion for $n = 1$).
Edit: Actually, the partition need not to be into blocks of size $1$ and $n-1$. Any other partition will work equally well and with precisely the same argument.
