To find nonlinear invariant of S box I read a paper about a nonlinear invariant attack that is Y.Todo et. al's "Nonlinear Invariant Attack: Practical Attack on Full SCREAM, iSCREAM, and Midori64" 

In this paper's Appendix A., they said that 


  Then, by Gaussian elimination like computation, we compute matrix $M'=[M_1'\|M_2']. $ If rows of $M_2'$ are $[0,0,...,0]$ or $[1,0,0,...,0]$, the corresponding row of $M_1'$is the basis of $U(S)$ 


I wonder why that is the basis of $U(S)$.

In my thinking corresponding row of $M_1'$ such that the row of $M_2'$ are $[1,0,0,...,0]$ or $[0,1,0,0,...,0]$ or $...$ or $[0,0,0,...,0,1]$ is the basis of $U(S)$.

Can you show me why "If rows of $M_2'$ are $[0,0,...,0]$ or $[1,0,0,...,0]$, the corresponding row of $M_1'$ is the basis of $U(S)$" is right.
Keep this fact. 

By linear algebra, we can know that $M'_{1} \times M=M'_{2}$.

Let $\beta _i$ be a row of $M'_{1}$ which is correspond to $M'_2$ 's $[0,\ldots,0]$ row 

and let  $\beta_i=[\beta_{0,i},\beta_{1,i},\ldots,\beta_{2^n-1,i}]$

Then we can know that $\beta_{i} \times M=[0,\ldots,0] $ by above fact. 

So, if we define $b_i(x)=\beta_{0,i}x^0 \oplus \beta_{1,i}x^1 \oplus \cdot\cdot\cdot \oplus \beta_{2^n-1,i}x^{2^n-1}$.

Then, 

\begin{align}
b_i(x)\oplus b_i(S(x))= &amp; \bigoplus_{u\in\mathbb{F}_2^n}\beta_{u,i}\big(x^u \oplus S(x)^u\big)\\
= &amp; \bigoplus_{u\in\mathbb{F}_2^n} \beta_{u,i}\big(\bigoplus_{v\in\mathbb{F}_2^n} \lambda_{u,v}x^v \big)\\
= &amp; \bigoplus_{u\in\mathbb{F}_2^n}\big(\bigoplus_{v\in\mathbb{F}_2^n}\beta_{u,i}\lambda_{u,v}\big)x^v\\
=&amp; 0 
\end{align}

We can apply this formula similarly to the case of $[1,0,\ldots,0]$.