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.

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.

• How do you arrive at $(1-P) \, C \, (c \, w_2 - d \, v_2) = 0$? And how do you conclude $c \, d = 0$? – gerw Oct 15 '15 at 11:58
• Ahh, I got it. But it involves a small calculation... – gerw Oct 15 '15 at 12:10

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.

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.

• In your matrix, you could replace $A_{1,1} \pm 1$ by $A_{1,1}+x$ and then compute the determinant. You will obtain an one degree polynomial. Thus, 1 and -1 can not be roots of this polynomial. Notice this approach works for any field with characteristic not equal to 2. This result is wrong if the field has characteristic 2. – Daniel Oct 15 '15 at 19:19
• @Daniel: Yes, this is a good point. It cannot be the zero polynomial, since $A_{2,2} + B_{2,2}$ is invertible. However, I like the approach with the Schur complement, because you can arbitrarily split the matrix. – gerw Oct 15 '15 at 20:55