Integer Program Combination Optimization - Lattices I

1 Outline Slide 1 Integer points in lattices. Is fx 2 Z n j Ax = bg nonempty? 2 Integer points in lattices B = b1 : : : bd] 2 Rn d, b1 : : : bd are linearly independent. L = L(B ) = fy 2 Rn j y = Bv v 2 Z d g is called the lattice generated by B . B is called a basis of L(B ). bi = ei, i = 1 : : : n ei is the i-th unit vector, then L(e1 : : : en) = Z n: x y 2 L(B) and   2 Z , x + y 2 L(B). 2.1 Multiple bases b1 = (1 2)0 b2 = (2 1)0, b3 = (1 ;1)0. Then, L(b1 b2) = L(b2 b3). x2 1 0 04 1 00 11 3 00 11 00 11 00 11 00 11 1 b 0 1 11 00 2 0 1 00 11 1 0 000 111 000 111 000 111 b3 000 111 1 112 00 1 0 00 11 00000 11111 000 111 b 00 11 00000 11111 000 111 00 11 00000 11111 000 111 00 11 00000 11111 000 111 11 00 1 0 1 2 4 x1 -2 -1 3 -1 1 0 1 0 11 00 00 11 0 1 00 11 0-2 1 1 Slide 2 Slide 3 2.2 Alternative bases Slide 4 2.3 Proof Slide 5 Let B =
b1 : : : bd ] be a basis of the lattice L. If U 2 Rd d is unimodular, then B = BU is a basis of the lattice L. If B and B are bases of L, then there exists a unimodular matrix U such that B = BU . If B and B are bases of L, then jdet(B )j = jdet(B )j. For all x 2 L: x = Bv with v 2 Z d . det(U ) = 1, and det(U ;1 ) = 1= det(U ) = 1. x = BUU ;1 v: From Cramer's rule, U ;1 has integral coordinates, and thus w = U ;1 v is integral. B = BU . Then, x = Bw, with w 2 Z d , which implies that B is a basis of L. B =d
b1 : : : bd ] be bases of L. Then, the vectors b1 : : : bd B =
b1 : : : bd ] and 1 and the vectors b : : : b are both linearly independent. n n V = fBy j y 2 R g = fBy j y 2 R g: There exists an invertible d  d matrix U such that B = BU and B = BU ;1 : bi = BU i U i 2 Z d and bi = BU ;i 1 U ;i 1 2 Z d U and U ;1 are both integral, and thus both det(U ) and det(U ;1 ) are integral, leading to det(U ) = 1. jdet(B )j = jdet(B )jjdet(U )j = jdet(B )j. : 2.4 Convex Body Theorem Let L be a lattice in Rn and let A 2 Rn be a convex set such that vol(A) > 2n det(L) and A is symmetric around the origin, i.e., z 2 A if and only if ;z 2 A. Then A contains a non-zero lattice point. 2.5 Integer normal form A 2 Z m n ofmfullmrow rank is in integer normal form, if it is of the form
B 0], where B 2 Z is invertible, has integral elements and is lower triangular. Elementary operations: (a) Exchanging two columns (b) Multiplying a column by ;1. (c) Adding an integral multiple of one column to another. Theorem: (a) A full row rank A 2 Z m n can be brought into the integer normal form
B 0] using elementary column operations (b) There is a unimodular matrix U such that
B 0] = AU : 2 Slide 6 Slide 7 2.6 Proof We show by induction that by applying elementary column operations (a)-(c), we can transform A to
 0 (1) v C where  2 Z+ n f0g, v 2 Z m;1 and C 2 Z (m;1) (n;1) is of full row rank. By proceeding inductively on the matrix C we prove part (a). By iteratively exchanging two columns of A (Operation (a)) and possibly multiplying columns by ;1 (Operation (b)), we can transform A (and renumber the column indices) such that a1 1  a1 2  : : :  a1 n  0: Since A is of full row rank, a1 1 > 0. Let k = maxfi : a1 i > 0g. If k = 1, then we have transformed A into a matrix of the form (1). Otherwise, k  2 and by applying k ; 1 operations (c) we transform A to A = A1 ;  a1 1 a1 2  A2 ::: Ak;1 ;  k;1 a1 k a1  Ak Ak Ak+1 ::: An
: Repeat the process to A, and exchange two columns of A such that a1 maxfi : a1 i > 1  a1 2  : : :  a1 n  0: 0g  k k X i=1 a1 i k;1 X i=1 (a1 i ; a1 i+1 ) + a1 k = a1 1 < k X i=1 a1 i which implies that after a nite number of iterations A is transformed by elementary column operations (a)-(c) into a matrix of the form (1). Each of the elementary column operations corresponds to multiplying matrix A by a unimodular matrix as follows: (i) Exchanging columns k and j of matrix A corresponds to multiplying matrix A by a unimodular matrix U 1 = I + I k j + I j k ; I k k ; I j j . det(U 1 ) = ;1. (ii) Multiplying column j by ;1 corresponds to multiplying matrix A by a unimodular matrix U 2 = I ;2I j j , that is an identity matrix except that element (j j ) is ;1. det(U 2 ) = ;1. (iii) Adding f 2 Z times column k to column j , corresponds to multiplying matrix A by a unimodular matrix U 3 = I + f I k j . Since det(U 3 ) = 1, U 3 is unimodular. Performing two elementary column operations corresponds to multiplying the corresponding unimodular matrices resulting in another unimodular matrix. 3 Slide 8 2.7 Example Slide 9 3 1
;4 2 0 7 4 3 2 0 1 7 ;! 1 ;1 1 2 ;6 7 Reordering the columns


2 1 1 7 ;6 ;1 Replacing columns one and two by the dierence of the rst and twice the second column and the second and third column, respectively, yields 0 19 0 ;5 1 ;1 Reordering the columns
:
1 0 0 : ;1 19 ;5 Continuing with the matrix C =
19 ;5], we obtain successively, the matrices
19 5],
4 5],
5 4],
1 4]
4 1]
0 1] and
1 0]. The integer normal form is: 1 0 0 ;1 1 0
: 2.8 Characterization A 2 Z m n , full row rank
B 0] = AU . Let b 2 Z m and = fx 2 Z n j Ax = bg. (a) The set is nonempty if and only if B ;1 b 2 Z m Slide 10 S S (b) If =6 , every solution of is of the form S : S x = U 1 B ;1 b + U 2 z z 2 Z n;m where U 1 , U 2 : U =
U 1 U 2 ]. (c) L = fx 2 Z n j Ax = 0g is a lattice and the column vectors of U 2 constitute a basis of L. 2.9 Proof y = U ;1 x. Since U is unimodular, y 2 Z nnif and only if x 2 Z n . Thus, is nonempty if and only if there exists a y 2 Z such that
B 0]y = b Since B is invertible, the latter is true if and only B ;1 b 2 Z m S : : 4 Slide 11 We can express the set S as follows: n j Ax = bg S = fx 2 Z = fx 2 Z n j x = Uy
B 0]y = b y 2 Z n g = fx 2 Z n j x = U 1 w + U 2 z Bw = b w 2 Z m z 2 Z n;m g: Thus, if S 6= , then B ;1 b 2 Z m from part (a) and hence, n j x = U 1 B ;1 b + U 2 z z 2 Z n;m g: S = fx 2 Z Let L = fx 2 Z n j Ax = 0g. By setting b = 0 in part (b) we obtain that L = fx 2 Z n j x = U 2 z z 2 Z n;m g: Thus, by denition, L is a lattice with basis U 2 . 2.10 Example Slide 12 Is S = fx 2 Z 3 j Ax = bg is nonempty

A = 34 65 15 and b = 32 : Integer normal form:
B 0] = AU , with 9 ;25 # and U = ;4 11 : ;3 9 ; 1 0 2 Note that det(U ) = ;1. Since B b = (3 ;13) 2 Z , S 6= . All integer solutions of S are given by " " #
" ;25 # 0 9# ;117 ; 25z 3 x = 0 ;4 + 11 z = 52 + 11z ;13 1 ;3 9 42 + 9z
B 0] = 15 01 00
" 0 0 1 z 2 Z: 2.11 Integral Farkas lemma Let A 2 Z m n , b 2 Z m and S = fx 2 Z n j Ax = bg. The set S =  if and only if there exists a y 2 Qm , such that y0A 2 Z m and y0 b 2= Z . The set S =  if and only if there exists a y 2 Qm , such that y  0, y0A 2 Z m and y0b 2= Z . 2.12 Proof Assume that S 6= . If there exists y 2 Qm , such that y0 A 2 Z m and y0 b 2= Z , then y0 Ax = y0 b with y 0 Ax 2 Z and y0 b 2= Z . Conversely, if S = , then by previous theorem, u = B ;1 b 2= Z m , that is there exists an i such that ui 2= Z . Taking y to be the ith row of B ;1 proves the theorem. 5 Slide 13 Slide 14 2.13 Reformulations max c0 x x 2 S = fx 2 Z+n j Ax = bg :
B 0] = AU . There exists x0 2 Z n : Ax0 = b i B ;1 b 2= Z m . Let x2 S () x = x0 + y : Ay = 0 ;x0  y y L = f 2 Zn j Let U 2 be a basis of L, i.e., y L = f 2 Zn j max s:t Ay = 0g : y = U 2 z z 2 Z n; m g : c0 U 2 z U 2 z  ;x0 z 2 Z n;m : Dierent bases give rise to alternative reformulations c0 Bz Bz  ;x0 z 2 Z n;m max s:t: : 6 : Slide 15