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

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)?

• In other words, you are looking for an algorithm that conjugates a partition. – Yuval Filmus Jun 1 '19 at 12:58

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*}

• Why did you stop at 4 twice in the second example? – Vishal Sharma Jun 1 '19 at 16:55
• Oh.. it's because it satisfied the condition for 3 as well as 4 right? – Vishal Sharma Jun 1 '19 at 16:57
• Right, this is why I included this example. – Yuval Filmus Jun 1 '19 at 17:17

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)$$.

• In the pseudo-code, shouldn't array b be of length m? And btw, m = a[0], right? – Vishal Sharma Jun 3 '19 at 6:10
• *(a[0] is the first element of a) – Vishal Sharma Jun 3 '19 at 6:24
• @VishalSharma Yes, the length of b should be m not n. If I can assume that m is equal to the first element of a then I can make this code a bit simpler... Let me do just that. – MegaTom Jun 9 '19 at 2:04