For every square matrix $U$ there exist a diagonal matrix $E$ with $e_{i,i}=-1 , 1 $ such that $E U - I_n$ is non-singular 
For every square matrix $U$ there exist a diagonal matrix $E$ with $e_{i,i} = \pm 1$ such that

*

*$E U - I_n$ is non-singular.

*If $U$ is unitary then $EU$ is also unitary

Note that all computation is over coefficient modulo $3$.


I want to prove this statement, but have no idea how and where to start.
 A: To prove $EU-I_n$ non singular matrix it is sufficient to show that $0$ can't be an eigenvalue of $EU-I_n.$ or det$(EU-I_n) \ne 0$
Clearly $E^2=I_n,$
$EU-I_n$ $\Rightarrow$ $EU-E^2$
$E(U-E)$ (by distributive law of matrices),
$det(E(U-E))\ne 0$
$\Rightarrow$ $det(E).det(U-E)\ne 0$
and clearly $det(E)=\pm1,$
$det(U-E)\ne 0$
Claim: $0$ is not an eigenvalue of $U-E$.
Suppose
Case1: $1$ is an eigenvalue of $U$ with (A.M=$r_1$) then in that case take $-1$ with $r_1$ times entries in $E$ so that $0$ can't be eigenvalue of $E-U.$
case2: $-1$ is an eigenvalue of $U$ with (A.M=$r_1$) then in that case take $1$ with $r_1$ times entries in $E$ so that $0$ can't be eigenvalue of $E-U.$
case 3: $1$ (A.M.=$r_1$) and $-1$ (A.M=$r_2$) then take $-1$ (A.M.=$r_1$) and $1$ (A.M=$r_2$) entries (or which are same as eigenvalues of $E$)
and for any other eigenvalues except $\pm1$ of $U$ always gives nonzero eigenvalue of $U-E.$
Hence $EU-I_n$ is non singular matrix.
A: As other pointed out, since any diagonal $E$ with diagonal elements $1$ or $-1$ is its own inverse, $EU-I_n$ is singular iff $E^2U - E$ is singular, i.e. iff $U-E$ is singular.
We want to show that there exists $E$ with the given form such that $U-E$ is singular.
Now user1551 suggested to do it by Laplace expansion and induction. That is of course a very good way: assuming (induction) you can find the last $n-1$ elements of $E$ so that
$U_{2:n,2:n}-E_{2:n,2:n}$ is singular, a Laplace expansion along the first line gives $\det(U-E) = (U_{11}-E_{11})\det(U_{2:n,2:n}-E_{2:n,2:n})+cste$.
Now you see that if you take $E_{11}=1$ instead of $E_{11}=-1$, you change the determinant by $2\det(U_{2:n,2:n}-E_{2:n,2:n}) \neq 0$, so one of the two choices yield a non singular $U-E$.
The base case ($n=1$ or $n=0$, as you prefer) being obvious, that ends the induction.
Note that this proof keeps working if you choose $E$ with diagonal elements in $\{a,b\}$ (instead of $\{-1,1\}$, with two different elements $a, b$).

Regarding (ii), if $U$ is unitary, then $EU(EU)^T = EUU^TE^T=EI_nE^T=EE^T=E^2=I_n$.
A: To prove that $EU-I_n $ is a non-singular matrix, since $E^2=I_n$ then $EU-I_n=U-E.$
Suppose
\begin{equation*}
U=
\begin{pmatrix}
a_{11} & a_{12} \cdots & a_{1n} \\
a_{21} & a_{22}  \cdots & a_{2n} \\
\vdots\\ 
a_{n1} & a_{n2} \cdots & a_{nn} \\
\end{pmatrix}
\end{equation*}
and $E=diag(\sigma_1, \sigma_2 \dots \sigma_n)$ then
\begin{equation*}
U_{k+1}-E_{k+1}=
\begin{pmatrix}
a_{11}-\sigma_1 & a_{12} \cdots & a_{1k} & a_{1,k+1}\\
a_{21} & a_{22}-\sigma_2  \cdots & a_{2k} & a_{2,k+1}\\
\vdots\\ 
a_{k1} & a_{k2} \cdots & a_{k,k}-\sigma_k & a_{k,k+1} \\
a_{k+1,1} & a_{k+2,2} \cdots & a_{k+1,k} & a_{k+1,k+1}-\sigma_{k+1} \\
\end{pmatrix}_{k+1,k+1}
\end{equation*}
Now using Mathematical induction(PMI) and Schur's complement https://en.wikipedia.org/wiki/Schur_complement
https://en.wikipedia.org/wiki/Mathematical_induction
Apply PMI on the $U-E$ matrix we get,  obviously for $n=1$ is true,
and assume for $n=k$ that is
det$(U_k-E_k)\ne 0$
then for $n=k+1,$ $det(U_{k+1}-E_{k+1})=det(a_{k+1,k+1}-\sigma_{k+1}).det((a_{k+1,k+1}-\sigma_{k+1})-Y(U_k-E_k)^{-1}X)$
where $X=[a_{1,k+1},a_{2,k+1} \dots a_{k,k+1}]$ and $Y=[a_{k+1,1},a_{k+2,2} \dots a_{k+1,k}]$
clearly $det(a_{k+1,k+1}-\sigma_{k+1})\ne 0,$
Claim: $det((a_{k+1,k+1}-\sigma_{k+1})-Y(U_k-E_k)^{-1}X)\ne 0----(i)$
Let $Y(U_k-E_k)^{-1}X= Z$ then (i) beacome $det(a_{k+1,k+1}-Z-\sigma_{k+1}) \ne 0$
Case 1: if $a_{k+1,k+1}-Z =1 $ then take $\sigma_{k+1}=-1$ so that det$(U_{k+1}-E_{k+1}) \ne 0$
Case 2: if $a_{k+1,k+1}-Z =-1 $ then take $\sigma_{k+1}=1$ so that det$(U_{k+1}-E_{k+1} )\ne 0$
So it is true for $n=k+1$, Hence using principle of mathematical induction det$(U_n-E_n)\ne 0$
Hence $EU-I_n $ is non-singular matrix.
