Suppose $A$ is some set. Let's define a pair semigroup over $A$ as $P[A] = (A\times A \cup \{0\}, \circ)$, where the $\circ$ operation is defined by the following two identities:


1. $\forall a \in P[A]$ we have $a \circ 0 = 0 \circ a = 0$
2. $\forall (a, b, c, d) \in A\times A \times A \times A$ we have $(a, b) \circ (c, d) = \begin{cases} (a, d) & \quad b = c \\ 0 & \quad b \neq c\end{cases}$


Now, suppose $|A| = n$. Suppose $S \subset P[A]$, such that $S \circ S = P[A]$ (here $X \circ Y := \{x\circ y|x \in X, y \in Y\}$). What is the minimal possible $|S|$?


On one hand it is always true that $|S| \geq n$, as $n^2 + 1 = |P[A]| = |S \circ S| \leq |S \times S| = |S|^2$.


On the other hand $\exists S$ satisfying those conditions such that $|S| = 2n - 1$. It is $S\_a = \{(a,a)\} \cup \{(a, b)|b \in A \setminus \{a\}\} \cup \{(b, a)|b \in A \setminus \{a\}\}$ for any arbitrary $a \in A$. Do not know, however, whether $2n - 1$ is the desired minimum or not.



What is the minimal possible size of a subset of this semigroup satisfying the following conditions?
$|S|=2n-1$ is indeed minimal.


In graph theoretic terms, you are asking for the minimal number of edges of a directed graph $G$ on $n$ vertices such that there is a directed path of length two between each pair of vertices (which vertices may also agree).
(If n>1, we may safely forget about the zero element of the semigroup.)


Denote by $c\_i$ (resp. $d\_i$) the in-degree (resp. out-degree) of the vertex $i\in V(G)$. The number of directed paths of length two is at most $\sum\_{i\in V(G)}c\_i d\_i$, where $\sum\_i c\_i = \sum\_i d\_i = k$, the number of edges. The assumption implies $c\_i, d\_i \geq 1$ for all $i$. 
Forgetting about the graph, the value $\sum\_i c\_i d\_i$ is maximized with the given constraints only if $c\_i=d\_i=1$ for all but one $i$, and $c\_{i\_0}=d\_{i\_0}=k-n+1$ for the remaining $i\_0$. (Iteratively replace ($c\_i$, $c\_j$) with $(c\_i+c\_j-1, 1)$ for each pair of $(i,j)$, where $d\_i \geq d\_j$, and repeat this for $d\_i$'s too.) 


Then we get $(k-n+1)^2 + (n-1)1^2 \geq |\{\textrm{paths of length two}\}| \geq n^2$, i.e. $k\geq \sqrt{n^2-n+1}+n-1 > 2n-2$.


