# Resulting shapes when partitioning the constraint matrix $\boldsymbol{A}$ in linear programming

$$$$\boldsymbol{A} = \begin{bmatrix} {1}_n^\top \otimes \mathbb{I}_m \\ \mathbb{I}_n \otimes {1}_m^\top \end{bmatrix} \in \mathbb{R}^{(m+n)\times mn}$$$$

If the above matrix is partitioned as follows, are the dimensions shown below correct?

$$$$\boldsymbol{A}' = \begin{bmatrix} {1}_n^\top \otimes \mathbb{I}_m \end{bmatrix} \in \mathbb{R}^{m\times mn}$$$$

$$$$\boldsymbol{A}'' = \begin{bmatrix} \mathbb{I}_n \otimes {1}_m^\top \end{bmatrix} \in \mathbb{R}^{n\times mn}$$$$

If not, have I misinterpreted the steps to partitioning a block matrix? Can you then show how it can be corrected?

## 1 Answer

I would assume that $$\otimes$$ is the Kronecker product and that $$A'$$ refers to the first set of rows of $$A$$ (and not a transpose, as that notation is also often used - so that is not your question, I assume), i.e., that

$$A=\begin{pmatrix}A'\\A''\end{pmatrix}$$ Also, $$1_n$$ is an $$n$$-dimensional column vector, so that $$1_n^\top$$ is $$(1\times n)$$.

Then, the results follow from the definition of a Kronecker product, which say that the row dimension of $$C\otimes D$$ is the product of the row dimensions of $$C$$ and $$D$$, and likewise for the column dimension. Since $$1_n^\top$$ has row dimension 1 and $$\mathbb{I}_m$$ has row-dimension $$m$$, $${1}_n^\top \otimes \mathbb{I}_m$$ has row-dimension $$m$$. The same reasoning leads to $$n$$ rows for $$A''$$, so $$n+m$$ rows in total.

Since $$1_n^\top$$ has $$n$$ columns and $$\mathbb{I}_m$$ has $$m$$, the column dimension is, analogously, $$mn$$.

• so what I wrote is right, or did I get the columns $mn$ shape wrong – develarist Dec 4 '20 at 9:36
• the column dimension is indeed $mn$, please see my edit – Christoph Hanck Dec 4 '20 at 10:39
• in the answer to the following question, i try to correct someone else's take on $A'$ and $A''$'s column dimension. hope you also agree there, although I see now I misled them by incorrectly stating what $A$'s dimensions were in the comments due to a faulty source, which I then re-state in a later comment math.stackexchange.com/questions/3929230/… – develarist Dec 4 '20 at 10:43
• Assuming you refer to the penultimate comment there, yes, the column dimension should also be $mn$. – Christoph Hanck Dec 4 '20 at 11:26