I have a square matrix $G$ of size $n \times n$ in which each column is a random permutations of $[1,n]$, for example:
1 1 3 4
2 2 1 1
3 3 2 2
4 4 4 3
when $n=4$.
My question is, can I always find a number between $1$ and $n$, call it $x$, such that:
For any other number between 1 and $n$, call it $j$, I can find a column in which $x$ appears after $j$, and the columns are different for each $j$?
For example, in the matrix above, the answer is yes. The value $x=4$.
Because in column $1$, $2$ is above $4$.
In column $2$, $1$ is above $4$.
And in column $3$, $3$ is above $4$.
Can I always find the number $x$ in any given matrix composed of permutations? And how many $x$'s can I find?
Let us prove it by induction on $n$. This is trivial for $n = 1$. Now, assume it is true at rank $n$. Let $G = (\sigma_j(i))_{1 \leqslant i,j \leqslant n + 1}$ where each $\sigma_i$ is a permutation of $[\![1,n + 1]\!]$.
Let $a = \sigma_{n + 1}(1)$ be the integer that appears at the top right of $G$. Consider $H$ the matrix formed of the elements of $G$ where all the $a$ and the last column has been removed. Formally, $H = (\tilde{\sigma}_j(i))_{1 \leqslant i,j \leqslant n}$, where \begin{align*} \tilde{\sigma}_j(i) & = \sigma_j(i) \textrm{ if } i < \sigma_j^{-1}(a),\\ \tilde{\sigma}_j(i) & = \sigma_j(i - 1) \textrm{ if } i \geqslant \sigma_j^{-1}(a) \end{align*} Each $\tilde{\sigma}_j$ is a permutation of $[\![1,n + 1]\!]\backslash\{a\}$ so up to relabelling the coefficients of $H$, it verifies the wanted hypothesis and it has size $n \times n$. By induction, there exists an $x \in [\![1,n + 1]\!]\backslash\{a\}$ and an injective function $\rho : [\![1,n + 1]\!]\backslash\{a,x\} \rightarrow [\![1,n]\!]$ such that for all $i \in [\![1,n + 1]\!]\backslash\{a,x\}$, $i$ appears before $x$ in the column $\rho(i)$. In other words, $\tilde{\sigma}_{\rho(i)}^{-1}(i) < \tilde{\sigma}_{\rho(i)}^{-1}(x)$.
Notice that it implies that $\sigma_{\rho(i)}^{-1}(i) < \sigma_{\rho(i)}^{-1}(x)$. In other words, this property remains true in $G$. Extend $\rho$ with $\rho(a) = n + 1$ and notice that $\sigma_{\rho(a)}^{-1}(a) = \sigma_{n + 1}^{-1}(a) = 1 < \sigma_{n + 1}^{-1}(x) = \sigma_{\rho(a)}^{-1}(x)$ ($a$ apprears before $x$ in the last column).
It proves that $x$ fits because for all $i \in [\![1,n + 1]\!]\backslash\{x\}$, $\sigma_{\rho(i)}^{-1}(i) < \sigma_{\rho(i)}^{-1}(x)$, meaning that $i$ appears before $x$ in the column $\rho(i)$, and $\rho$ is injective. Actually, I think we can pretty easily adapt the proof to show that $n - 1$ columns are enough.