Double summation

Question

I'm currently solving some Operations Research exercises related to Integer Programming. In one of the solutions of the exercises the author uses the following formula for the objective function:

$\sum_{i=1}^{m} \sum_{j=1}^{n} C_{ij} x_{ij} $

and for the constraints it uses the following:

$\sum_{i=1}^{m} x_{ij} = d_j , (j = 1,2,.., n) $

My question is twofold:

1. What is the meaning of the double summation in the objective function?
2. Could we use the double summation in the constraint, instead of using this $ (j = 1,2,.., n) $ ?

I hope my question is clear enough. If not I will try to put in different terms. Thank you very much in advance.

Answer 1

1. It means you sum over all combinations of $i$ and $j$. If $m=3$ and $n=4$ you'll have 12 summands in the sum.

2. No. There are $n$ constraints and that's very different from adding them all up and having just one constraint. You must have $\sum x_{i1} = d_1$ and also $\sum x_{i2} = d_2$ etc.

Answer 2

The first means you have two matrices $x$ and $C$, you take the transpose of $x$ and multiply it by $C$ (meaning matrix multiplication, not componentwise or Hadamard multiplication) and finally take the trace. So

$$\sum_{i=1}^{m} \sum_{j=1}^{n} C_{ij} x_{ij} = \text{tr}(C x^{\text{T}})$$

For the second, no. You have $n$ constraints, summing them would reduce it to 1 constraint (moreover dependent on the other $n$.)

Answer 3

1. I suggest you view the summation layer by layer, ie, fixing the outer layer index, in this case, $i$, say $i = 1$, then the inner layer summation is $\displaystyle \sum^{n}_{j=1} C_{1j} x_{1j} = (C_{11},\ldots,C_{1n}) \cdot (x_{11},\ldots,x_{1n})^T$, you could view this as the first row of matrix $C = (C_{ij})$ multiplying with the first column of transpose matrix of $x = (x_{ij})$, and the result is the 1st entry on the diagonal of the product matrix $C x^T$. Now thinking $i$ runs from 1 to $m$, you will get the summation of all the entries on the diagonal, which is the trace of $C x^T$; it is easier to understand if you visualize it as matrix product $C x^T$, an $m \times n$ matrix $C$ multiplying with an $n \times m$ matrix $x^T$ : $$ C x^T = \begin{pmatrix} C_{11} & C_{12} & \cdots & C_{1n} \\ C_{21} & C_{22} & \cdots & C_{2n} \\ &&\cdots& \\ C_{m1} & C_{m2} & \cdots & C_{mn} \end{pmatrix} \cdot \begin{pmatrix} x_{11} & x_{12} & \cdots & x_{m1} \\ x_{12} & x_{22} & \cdots & x_{m2} \\ \vdots&\vdots&&\vdots \\ x_{1n} & x_{2n} & \cdots & x_{nm} \end{pmatrix} $$ when you fix an $i$, then the summation with respect to $j$ is the $i$th row multiplying with the $i$th column of above matrix multiplication.

2. No, the constraint is essentially saying: when you fix $j$( $j$ is the column index of the matrix $x = (x_{ij})$, also the row index of the matrix $x^T = (x_{ji})$), the sum of the entries on $j$th row of the matrix $x^T$ is a given number $d_j$; visualizing it as equation system would be like $$ \left\{ \begin{eqnarray} x_{11} + x_{21} + \cdots + x_{m1} &= d_1 \\ x_{12} + x_{22} + \cdots + x_{m2} &= d_2 \\ \cdots& \\ x_{1n} + x_{2n} + \cdots + x_{mn} &= d_n \end{eqnarray} \right. $$ if you do the summation again, it will enlarge the solution space of $x$ dramatically, the optimization of the utility function may yield a different result.