I've put this question on mthoverflow also. Here I put the link: https://mathoverflow.net/questions/324172/determinant-of-the-sum-of-a-left-circulant-and-a-nonsingular-matrix-over-field-o
For any matrix $A=(a_{ij})\in M_n(\mathbb{F}_2)$, denote $\bar{A}=(\bar{a_{ij}}),$ where $\bar{a}=0$ if $a=1$ and $\bar{a}=1$ if $a=0$. Suppose $n$ is a power of two. Let $A$ (left circulant) and $I'$ be $n\times n$ matrices over $\mathbb{F}_2$ defined by, $$X=\begin{pmatrix} x_1 & x_2 & x_3 &\ldots & x_{n-1} &x_n \\ x_2 & x_3 & x_4 &\ldots & x_{n} &x_1 \\ x_3 & x_4 & x_5 &\ldots & x_{1} &x_2 \\ & & &\vdots \\ x_{n-1} & x_n & x_1 &\ldots & x_{n-3} &x_{n-2} \\ x_n & x_1 & x_2 &\ldots & x_{n-2} &x_{n-1} \end{pmatrix}, I'= \begin{pmatrix} 0 & 0 & 0 & \ldots & 0 & 0 \\ 0 & 0 & 0 & \ldots & 0 & 1 \\ 0 & 0 & 0 & \ldots & 1 & 1 \\ & & & \vdots \\ 0 & 0 & 1 & \ldots & 1 & 1 \\ 0 & 1 & 1 & \ldots & 1 & 1 \end{pmatrix}.$$ Then it seems either $X+I'$ or $X+\bar{I'}$ is invertible. But I cannot prove that. Is there any simple method to prove this?