Вариант с перебором уж слишком плох, мне хотелось бы, что либо работающее за полиномиальное время. А как вы думаете следует убирать заведомо плохие варианты?
Еще эта задача есть и в более сильной постановке, а именно, матрица

не обязана состоять из столбцов матриц

. В этом случае не получается применять даже перебор.