2
$\begingroup$

This is the generalization of a question Is a simple graph the "sum" of a partial order and its dual?

Nik Weaver found a counterexample in a very nice, complete (and instantaneous!) answer, so I modify the question to hope for a yes.

(I changed the old $S$ of previous question in $G$ in this question )

A "$n$-graph matrix" $G\in M_n(\mathbb F_2)$ is a symmetric matrix such that $G_{ii}=0$ for all $i\in [1,n]$

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$

Let's add $m\in \mathbb N$ full zero first rows and $m$ full zero last columns to an $n$-order matrix then we will call it a $(m+n)$-schiftordered matrix. (since $m$ can be $0$, an ordered matrix is a schiftordered matrix)

Is it true that for any "$n$-graph matrix" $G$ there exists a "$n$-schiftordered matrix" $Z$ s.t. $G=Z+Z^t$ ?

(Note that if $S$ is the one that occures in Nik Weaver answer then $Z$ defined by $Z_{ij}=S_{ij}$ if $i>j$ and $0$ if not, satisfies $Z+Z^t=S$ and $Z$ is a $5$ -shiftordered matrix)

$\endgroup$
3
  • 1
    $\begingroup$ The time I spent trying to parse the mis-spelled original title surely would have similarly consumed waaaay too much mental energy from other people, too! So had to repair it... :) $\endgroup$ Jul 21, 2018 at 23:05
  • 1
    $\begingroup$ It seems that essentially the same counting argument applies as the one for the previous question (mathoverflow.net/q/306562). $\endgroup$
    – Jan Kyncl
    Jul 21, 2018 at 23:13
  • $\begingroup$ That's true!! Can you please put it as an answer! Then I could accept it! $\endgroup$
    – jcdornano
    Jul 21, 2018 at 23:24

1 Answer 1

3
$\begingroup$

Expanded comment: It seems that essentially the same counting argument applies as the one for the previous question (mathoverflow.net/q/306562):

We can make first $m$ rows and last $m$ columns of an $n\times n$ matrix zero in $n+1$ different ways, this increases the total number of matrices $S$ at most $(n+1)$ times.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.