Question

Determine whether the relations represented by given zero-one matrices are partial orders.

Short answer

The relation represented by the matrix \(\left( {\begin{array}{*{20}{l}}1&1&1&0\\0&1&1&0\\0&0&1&1\\1&1&0&1\end{array}} \right)\) is not a partial ordering.

Step-by-step solution

Given data

The matrix, \(\left( {\begin{array}{*{20}{l}}1&1&1&0\\0&1&1&0\\0&0&1&1\\1&1&0&1\end{array}} \right)\).

Concept used of partially ordered set

A relation\(R\)is a poset if and only if,\((x,x)\)is in\({\rm{R}}\)for all x (reflexivity)

\((x,y)\)and \((y,x)\) in R implies \(x = y\) (anti-symmetry),\((x,y)\) and \((y,z)\) in R implies \((x,z)\) is in \({\rm{R}}\) (transitivity).

Find  if the \(R\) is poset

Consider the matrix \(\left( {\begin{array}{*{20}{l}}1&1&1&0\\0&1&1&0\\0&0&1&1\\1&1&0&1\end{array}} \right)\).

From the above matrix, it is clear that \( \Rightarrow {m_{13}} = 1{m_{34}} = 1\), but \({m_{14}} = 0( \ne 1)\);so relation is not a transitive. Therefore, the relation represented by the given matrix is not a partial ordering.