What is the minimal possible size of a subset of this semigroup satisfying the following conditions? 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:


*

*$\forall a \in P[A]$ we have $a \circ 0 = 0 \circ a = 0$

*$\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.
 A: $|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$.
