Finding row wise sum of transpose of hv-convex binary matrix

Question

I'm stuck on a problem involving the Gale-Ryser Theorem. The problem's input gives me the row-wise sum of an hv-convex binary matrix(n*m).

e.g. I get {4,3,2,2,1} in the input. It's the row wise sum of the following matrix:

    1 1 1 1
    1 1 1 0
    1 1 0 0
    1 1 0 0
    1 0 0 0

To solve the problem, I have to find the row-wise sum of it's transpose.

i.e. I need to calculate {5,4,2,1}

1 1 1 1 1
1 1 1 1 0
1 1 0 0 0
1 0 0 0 0

Can it be achieved in less than O(n*m)?

Answer 1

A non-increasing sequence of integers is known as a partition. The operation you are describing is known as conjugation. Given a partition $\lambda_1,\ldots,\lambda_n$, you can compute its conjugate $\lambda'_1,\ldots,\lambda'_m$ as follows:

• Initialize a pointer $i$ at $n$.
• Set $\lambda'_1 = i$.
• Advance $i$ backwards until $\lambda_i \geq 2$.
• Set $\lambda'_2 = i$.
• Advance $i$ backwards until $\lambda_i \geq 3$.
• Set $\lambda'_3 = i$.
• ...
• Stop once $i = 1$.

As an example, here is how you apply this algorithm on $4,3,2,2,1$. $$ \begin{align*} &\begin{array}{ccccc} 4 & 3 & 2 & 2 & 1 \\ &&&& \uparrow \\ &&&& 5 \end{array} \\\hline &\begin{array}{ccccc} 4 & 3 & 2 & 2 & 1 \\ &&& \uparrow \\ &&& 4 \end{array} \\\hline &\begin{array}{ccccc} 4 & 3 & 2 & 2 & 1 \\ & \uparrow \\ & 2 \end{array} \\\hline &\begin{array}{ccccc} 4 & 3 & 2 & 2 & 1 \\ \uparrow \\ 1 \end{array} \end{align*} $$ It might happen that at some point $i$ doesn't advance at all. This is what happens if we apply this algorithm on $5,4,2,1$: $$ \begin{align*} &\begin{array}{cccc} 5 & 4 & 2 & 1 \\ &&& \uparrow \\ &&& 4 \end{array} \\\hline &\begin{array}{cccc} 5 & 4 & 2 & 1 \\ && \uparrow \\ && 3 \end{array} \\\hline &\begin{array}{cccc} 5 & 4 & 2 & 1 \\ & \uparrow \\ & 2 \end{array} \\\hline &\begin{array}{cccc} 5 & 4 & 2 & 1 \\ & \uparrow \\ & 2 \end{array} \\\hline &\begin{array}{cccc} 5 & 4 & 2 & 1 \\ \uparrow \\ 1 \end{array} \end{align*} $$

Answer 2

The row-wise sum of the transpose is just the column-wise sum of the original matrix. So, for inputs $a_1 \cdots a_n$ and outputs $b_1 \cdots b_m$, it looks something like this: $$ \begin{array}{c|c&c&c&lcr} & b_1=4 & b_2=2 & b_3=1 \\ \hline a_1=3 & 1 & 1 & 1 \\ a_2=2 & 1 & 1 & 0 \\ a_3=1 & 1 & 0 & 0 \\ a_4=1 & 1 & 0 & 0 \end{array} $$

Each output is equal to the number of rows long enough to reach it. Therefore, a value $a_k$ affects the first $a_k$ outputs.

---

Algorithm description

First, initialize a vector of length $m$ called $b$, setting all elements to $0$. Next, for each element $a_i$ in $a$, increment $b_{a_i}$ by one. (this is the last element to be affected by $a_i$.)

Next, we will iterate backward over $b$, adding the next element and storing the result back into $b$. This effectively sums all higher elements in the old $b$.

Pseudocode:

conjugate(array a, int n, int m)
  b = new Array length m (all zeros)

  for i = 1 to n
    b[a[i]] += 1

  for i = m-1 downto 1
    b[i] += b[i+1]

  return b

Ruby Implementation

def conjugate(a)
  b = Array.new(a[0], 0)
  a.each do |x|
    b[x-1] += 1
  end
  (a[0]-2).downto 0 do |i|
    b[i] += b[i+1]
  end
  b
end

Try it online!

Efficiency

We have one loop over $a$ and one loop over $b$, giving $\Theta(n+m)$.