On the formulation of the linear assignment problem

Question

I'm looking at the standard definition of the assignment problem as defined here

My question is to do with the two constraints (latex notation follows):

\sum_{j=1}^n(x_{ij}) = 1 for all i = 1, ... , n
\sum_{i=1}^n(x_{ij}) = 1 for all j = 1, ... , n

Specifically, why the second constraint required? Doesn't the first already cover all pairs of x_{ij}?

Answer 1

Consider the matrix x_ij with the i ranging over the rows, and j ranging over the columns.

The first equation says that for each i (that is, for each row!) the sum of values in that row equals 1.

The second equations says thta for each j (that is, for each column!) the sum of values in that column equals 1.

Answer 2

No. Given that all the entries in X are 0 or 1, one constraint says 'there is exactly one 1 in each column' - the other says 'there is exactly one 1 in each row' (I always forget which way round matrix subscripts conventionally go). These statements have independent truth values.

Answer 3

This is not even remotely a programming problem. But I'll answer it anyway.

The first is a sum over j, for EACH value of i. The second is a sum over i, for EACH value of j.

So essentially, one of these constraint sets requires that the sum across the rows of the matrix x_{i,j} matrix must be unity. The other constraint is a requirement that the sum down the columns of that matrix must be unity.

(edit) It seems that we are still not being clear here. Consider the matrix

[0 1]
[0 1]

One must agree that the sum across the rows of this matrix is 1 for each row. However, when you form the sum of the elements of the first column, it is zero, and the sum of the elements in the second column, we find 2.

Now, consider a different matrix.

[0 1]
[1 0]

See that here, the sum over the rows or down the columns is always 1.