# The (minimum) rank of a relation

$\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 critical in 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.

• I am curious as to how this problem arose. – Nik Weaver Jun 26 '17 at 11:54
• @NikWeaver: this is, basically, an attempt to solve this problem:mathoverflow.net/questions/266531/…. You can replace the elements $a_{ij}$ by zeroes as long as this can be done without enlarging the rank. Thus, one needs to understands what happens when the rank must grow. – Seva Jun 26 '17 at 12:28
• It seems that any proper sub-relation of a critical relation must also be critical. And equivalence relations are critical as you said. So "critical" relations form a "independence system" at the least. – Pushpendre Jun 27 '17 at 8:26
• Unfortunately, "critical" relations do not form a matroid as shown by the counter-example, Let $S=\{(i,i) \mid 1 \le i \le 5\}$, $A = S \cup \{(1,2), (2,3), (3,1)\}$, and $B = S \cup \{(4,5), (5,4)\}$. There does not exist any element $x \in \{(1,2), (2,3), (3,1)\}$ such that $\{x\} \cup B$ will be critical. – Pushpendre Jun 27 '17 at 8:41
• @Pushpendre: the complete relation $\{(1,1),(1,2),(2,1),(2,2)\}$ in $\mathcal R_2$ is critical, but its proper subrelation $\{(1,1),(1,2),(2,2)\}$ is not. – Seva Jun 27 '17 at 9:45