Assume that the input space to be all the entries in the

by

(binary) matrix, and each hypothesis is simply sign(

) for two matrices of rank at most

. The following paper

http://ttic.uchicago.edu/~nati/Publi...kolaNIPS04.pdf
gives a combinatorial upper bound on the growth function, and thus the VC dimension is bounded by

some log factors. Hope this helps.