Let A be a fixed integer matrix of size m by n and consider all b for which the body is full dimensional. We examine the set of shortest non-zero integral vectors with respect to the family of norms. We show that the number of such shortest vectors is polynomial in the bit size of A, for fixed n. We also show the existence, for any n, of a family of matrices M for which the number of shortest vectors has as a lower bound a polynomial in the bit size of M of the same degree at the polynomial bound.