Timeline for Prove that there is a diagonal matrix $D$ with entries equal to $\pm 1$ such that $\det(A+D) \neq 0$
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 3, 2017 at 21:34 | comment | added | fedja | @FedorPetrov Agreed 100%. However you will be surprised to learn how many people see it from one perspective but not from the other. ;-) | |
| Jun 3, 2017 at 15:25 | comment | added | Fedor Petrov | @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. | |
| May 27, 2017 at 19:25 | comment | added | Christian Remling | 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.) | |
| May 27, 2017 at 16:08 | comment | added | Lewi_Sol | Can you expand on this idea and put as an answer? It is not so clear. | |
| May 27, 2017 at 14:00 | comment | added | fedja | 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...) | |
| May 27, 2017 at 7:43 | comment | added | Seva | Great solution! | |
| May 27, 2017 at 5:28 | history | answered | Gjergji Zaimi | CC BY-SA 3.0 |