4
$\begingroup$

I recently saw the following problem on an entrance exam:

Let $A$ be a square matrix. Prove that there is a diagonal matrix $D$ whose diagonal entries are either $+1$ or $-1$ such that $\det(A+D) \neq 0$.

I have no idea how to deal with the determinant of a sum of matrices. I think it can be proved by contradiction. But I don't see what would lead to if $\det(A+D)=0$ for all diagonal matrix $D$ with diagonal entries $\pm 1$. Hope someone could help me with this one. Thanks!

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ I don't think it's appropriate to use MO to get help with finding solutions for entrance exams or competition problems $\endgroup$
    – Yemon Choi
    Commented May 27, 2017 at 4:37
  • $\begingroup$ Sorry, I rarely use MO, could you tell me what kind of problem is appropriate to ask here, and why entrance exam or competition problem are inappropriate to ask? $\endgroup$
    – user50190
    Commented May 27, 2017 at 4:51
  • 5
    $\begingroup$ So it's not appropriate because this site is for problems that arise in people's original research; and not answering homework/competition/exam problems. You probably could ask at math.stackexchange.com. BTW: which entrance exam was this? It's quite an interesting problem. $\endgroup$
    – Anthony Quas
    Commented May 27, 2017 at 5:03
  • 2
    $\begingroup$ Oh! Now I see the difference between MO and Stackexchange, thanks! BTW, IT IS an interesting problem! It's from my friend, it's probably a problem of entrance exam for graduate school in Taiwan. $\endgroup$
    – user50190
    Commented May 27, 2017 at 5:11

2 Answers 2

Reset to default
6
$\begingroup$

Here is a non-inductive, and maybe slightly instructive, proof. Let $a_1,a_2,\dots, a_n$ and $b_1,b_2,\dots,b_n$ be numbers such that $a_i\neq b_i$ for all $i$. Let $X$ be the diagonal matrix with diagonal entries the variables $x_1,x_2,\dots,x_n$. Since the determinant $\det(A+X)$ is a polynomial with highest degree term $x_1x_2\cdots x_n$, combinatorial nullstellensatz tells us that we can make the determinant nonzero by choosing a value for each $x_i\in \{a_i,b_i\}$. Your problem is the special case $a_i=1,b_i=-1$ for all $i$.

Improve this answer
$\endgroup$
6
  • 2
    $\begingroup$ Great solution! $\endgroup$
    – Seva
    Commented May 27, 2017 at 7:43
  • $\begingroup$ Another instructive solution: if the Fourier expansion of the function $f$ on the discrete cube $\{-1,1\}^n$ (with respect to the standard basis $X_I=\prod_{i\in I}x_i$, $I\subset\{1,\dots,n\}$ is non-trivial, then $f$ is not identically zero. Not that one is supposed to know such methods on the entrance exams (except, perhaps, if you are in France and try to go to ENS Paris...) $\endgroup$
    – fedja
    Commented May 27, 2017 at 14:00
  • $\begingroup$ Can you expand on this idea and put as an answer? It is not so clear. $\endgroup$
    – Lewi_Sol
    Commented May 27, 2017 at 16:08
  • $\begingroup$ One doesn't really need any fancy tools to see that $p(x)=\sum c_{\alpha}x^{\alpha}$, with $\alpha_j=0$ or $1$ for all multi-indices, can't be identically zero on $x_j=\pm 1$ unless it's the zero polynomial. Just write $p=x_nq+r$ with $q,r$ polynomials of this type in the first $n-1$ variables, take $x_n=\pm 1$, and add and subtract. (This is another induction, so if these are declared uncouth, then this won't convince.) $\endgroup$
    – Christian Remling
    Commented May 27, 2017 at 19:25
  • $\begingroup$ @fedja it is essentially the same solution, both are based on the summation of $\det(A+X)\prod x_i$ over all diagonal matrices $X=diag(x_1,\dots,x_n)$, $x_i=\pm 1$. If we expand the determinant in $x_i$'s and sum up each term, only the term $\prod x_i$ survives. You may call it Combinatorial Nullstellensatz or Fourier transform of a function on the cube. $\endgroup$
    – Fedor Petrov
    Commented Jun 3, 2017 at 15:25
3
$\begingroup$

I can not comment because of low reputation stuff. So, please check this here

https://math.stackexchange.com/questions/1480091/show-that-there-exists-a-diagonal-matrix-b-the-diagonal-entries-of-which-are/1481391

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ Well, interesting. I was just starting to think about this, had no recollection of my earlier answer... $\endgroup$
    – Christian Remling
    Commented May 27, 2017 at 5:24
  • 1
    $\begingroup$ It happened to me before (I guess everyone else, too). :-) $\endgroup$
    – Lewi_Sol
    Commented May 27, 2017 at 5:33
  • 1
    $\begingroup$ And then they say you can learn things on MO/MSE... $\endgroup$
    – Christian Remling
    Commented May 27, 2017 at 5:35
  • 1
    $\begingroup$ Perhaps, the more we learn, the more we forget ... $\endgroup$
    – Lewi_Sol
    Commented May 27, 2017 at 5:36

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