A "$n$-order matrix" $T\in M\_n(\mathbb F\_2)$ is a matrix such that there exists a partial ordered relation $\leq\_T\subset [1,n]^2$ such that :


$T\_{ij}=1\Leftrightarrow i\leq\_T j$


(where $T\_{ij}$ is the $i,j$ coefficient of $T$)


A "$n$-graph matrix" $S\in M\_n(\mathbb F\_2)$ is a symmetric matrix such that $S\_{ii}=0$ for all $i\in [1,n]$


(where $G^t$ is the transposed matrix of $G$)



> 
> Is it true that for any "$n$-graph matrix" $S$ there exists a "$n$-order matrix" $T$ s.t. $S=T+T^t$ ?
> 
> 
> 



Is a simple graph the "sum" of a partial order and its dual?
Even with $0$'s on the diagonal it's still false. Consider the matrix $S = \left[\begin{matrix}0&1&0&0&1\cr 1&0&1&0&0\cr 0&1&0&1&0\cr 0&0&1&0&1\cr 1&0&0&1&0\end{matrix}\right]$. Suppose $S = T + T^t$ for some order matrix $T$. Then this order must have either $1 < 2$ or $2 < 1$ since $s\_{12} = 1$. Wlog say $1 < 2$. Similarly we must have $2 < 3$ or $3 < 2$.


Suppose $2 < 3$. Then $1 <2 < 3$, and hence $t\_{13} = 1$, but $s\_{13} = 0$ so this implies that $t\_{31} = 1$, i.e., $3 < 1$. If a "partial order" is antisymmetric this is impossible, but even if you allow $1 < 3 < 1$ we then get $2 < 3 < 1$, so that $t\_{12} = t\_{21} = 1$ and this contradicts $s\_{12} = 1$. So $2 < 3$ is impossible.


We have shown that $1 < 2$ implies $3 < 2$, and similarly $2 > 3$ implies $4 > 3$, and then $3 < 4$ implies $5 < 4$.


But what is the relation between $1$ and $5$? Since $s\_{15} = 1$ we need either $1 < 5$ or $5 < 1$. Wlog say $1 < 5$. Then $1 < 5 < 4$ so $t\_{14} = 1$, but since $s\_{14}= 0$ this forces $t\_{41} = 1$, i.e., $4 < 1$. Again this contradicts antisymmetry, but even if you drop antisymmetry it forces $5 < 4 < 1$ so that $t\_{51} = t\_{15} = 1$ and this contradicts $s\_{15} = 1$. So $S = T + T^t$ is impossible.


