<s>[INST] Finding the Smallest Convex Hull of an Adjacency Matrix Let's say I have a an adjacency matrix of a directed graph, with at most one 1 in each row (self-loops are allowed but are 1, not 2). My goal is to rearrange the matrix using only row and column swaps. If I treat the positive entries as points, I can shrink the size of the convex hull by putting empty columns and rows at the ends. But, I don't know if that admits the smallest cluster. How do I know if the convex hull is the smallest possible without using brute force?
Here is an example:
We have the 9X9 adjacency matrix,
\begin{Vmatrix}
0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0  \\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\
\end{Vmatrix}
which with dots is: 
\begin{Vmatrix}
  &   &   &   & \cdot &   &   &   &   \\
  &   &   &   &   & \cdot &   &   &    \\
\cdot &   &   &   &   &   &   &   &   \\
  &   &   &   &   & \cdot &   &   &   \\
  &   &   &   &   & \cdot &   &   &   \\
  &   &   &   &   &   &   &   &   &\\
\cdot &   &   &   &   &   &   &   &   \\
\cdot &   &   &   &   &   &   &   &   \\
  &   &   & \cdot &   &   &   &   &   \\
\end{Vmatrix}
then rearranged is:
 \begin{Vmatrix}
  & \cdot &   &   &   &   &   &   &   \\
  &   & \cdot &   &   &   &   &   &    \\
\cdot &   &   &   &   &   &   &   &   \\
  &   & \cdot &   &   &   &   &   &   \\
  &   & \cdot &   &   &   &   &   &   \\
\cdot &   &   &   &   &   &   &   &   \\
\cdot &   &   &   &   &   &   &   &   \\
  &   &   & \cdot &   &   &   &   &   \\
  &   &   &   &   &   &   &   &   \\
\end{Vmatrix}
with the convex hull of the latter clearly having the smaller area.
 [/INST] This isn't a proof. I noticed that we can treat each row as an integer since it has at most one 1 in a row. The column position of the one gives us the value, with the zero row being 0. We can then sort numbers based on how many duplicates there are for that number. So, if we have 1,2,4,4,4,5,5,6,6,6 we can sort it to,
4,4,4,6,6,6,5,5,2,1. We then make the first value 1's, the next new value 2's, and so on. This would give us 1,1,1,2,2,2,3,3,4,5. Then we can do our first step backwards. I am not sure if this always works though.
</s>