Determinant of (0,1)matrix which is reflexive, transitive, but not anti-symmetric

graph theorylinear algebra

It should be quite easy to show that if you represent the directed graph of a reflexive, transitive, and anti-symmetric relation as a binary adjacency matrix, the matrix will be invertible.

I believe it to be true (though I don't know for sure) that a matrix which is both reflexive and transitive, but is not anti-symmetric (that is, there is at least one case where $a_{ij}=1\ \text{and}\ a_{ji}=1, i\ne j$) must be non-invertible i.e. have determinant of zero.

The reason I believe it to be true, currently, is that I have generated thousands of such matrices and computed their determinants. So far there is not a single counter-example.

This is part of work I'm doing on an undergraduate project. I just wanted to reach out and see if anyone who actually works with this kind of stuff knows anything about whether what I'm talking about is already a known fact (can't find anything this specific just googling) and already proven, or if such a proof is beyond the scope of this project.

Best Answer

If $aRb$ (that is, $a$ is related to $b$), and $bRa$ (so there's your symmetric pair), then $aRc$ if and only if $bRc$ by transitivity, so the row for $a$ is identical to the row for $b$, so the determinant is zero.

Related Question