$\DeclareMathOperator{\rk}{rk}$

For an integer $n\ge 1$, let $\mathcal R_n$ denote the set of all reflexive binary relations on $[n]$. I define the *rank* of a relation $R\in\mathcal R_n$ to be the smallest possible rank of a square, real matrix of order $n$, supported on $R$ and having its diagonal elements non-zero; that is, the smallest possible rank of a matrix $(a_{ij})_{1\le i,j\le n}$ with $a_{ii}\ne 0$ and $a_{ij}=0$ whenever $(i,j)\notin R$.

Thus, for example,

- The complete relation $[n]^2$ (and only it) has rank $1$.
- Any acyclic relation, including the identity relation, has rank $n$ (one can always extend an acyclic relation to a linear order relation, corresponding to triangular matrices after an appropriate permutation of the rows / columns). Moreover, it is not difficult to see that acyclic relations are the
*only*relations of rank $n$. - The rank of an equivalence relation is equal to the number of induced equivalence classes.

Denoting the rank of a relation $R\in\mathcal R_n$ by $\rk(R)$,

Is it possible to classify the relations $R\in\mathcal R_n$ which are

criticalin the sense that $\rk(R')>\rk(R)$ for any proper (reflexive) sub-relation $R'\subset R$?

It is easily seen that every equivalence relation is critical, as well as every relation which is a union of the identity relation and a single cycle $\{(i_1,i_2),\dotsc,(i_{k-1},i_k),(i_k,i_1)\}$ with $i_1,\dotsc i_k\in[n]$ pairwise distinct.

One can construct critical relations observing that if $R=R_1\oplus R_2$, then $\rk(R)=\rk(R_1)+\rk(R_2)$; therefore, $R$ is critical if and only if so are both $R_1$ and $R_2$. This allows one to distinguish between *primitive* and *induced* critical relations.

For $n=2$, there is a unique primitive critical relation; namely, the complete relation $[2]^2$. For $n=3$, up to permutations, there are just two primitive critical relations: the complete relation $[3]^2$ and the relation visualized as $$ \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \end{bmatrix}. $$

As a last remark: I am aware of the notion of the minimum rank of a graph, but in my context the things look rather different.

mustgrow. $\endgroup$ – Seva Jun 26 '17 at 12:28