I think that trying to treat this as a matrix is not contributing anything, instead treat it as collection of items, each with a list of numbers in.

The the algorithm splits into 3 sequential steps

1. Combine any items which can be combined according to your "valid combinations"
2. Sort the items. According to a comparison which sorts on the first item in the list of numbers, if either first numbers is None, move onto the second item in the list of numbers....., if there's no overlap they you don't care
3. Check that every column has been simultaneously sorted, if any are wrong then return false.

Then after the algorithm you can build a matrix again if you want.