7
$\begingroup$

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.

$\endgroup$

3 Answers 3

1
$\begingroup$

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.

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

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Daniel
    Commented Oct 15, 2015 at 19:19
  • $\begingroup$ @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. $\endgroup$
    – gerw
    Commented Oct 15, 2015 at 20:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .