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

1. $E U - I_n$ is non-singular.
2. 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.

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.

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.

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$.