# 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
Commented Oct 15, 2015 at 11:58
• Ahh, I got it. But it involves a small calculation...
– gerw
Commented Oct 15, 2015 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. Commented Oct 15, 2015 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
Commented Oct 15, 2015 at 20:55