Возникла еще идея решения.
Допустим, у нас матрица

размером

и на ней заданы

пар равенств коефициентов.
Определим вектор

размерности

для каждого условия

(если

и

) таким образом:
Для всех коефициентов

, которые не состоят в равенствах, вектор задается так:
1. 
2. 
Далее, считаем вектора

и

совместимыми, если

и значения в векторах не повторяются (кроме 0). В таком случае, если мы найдем

попарно совместимых векторов - они точно будут соответствовать строкам перестановочной матрицы. Но может быть и меньшее количество (если к-во пар коефициентов, задействованых в условиях, будет ровно

, то требуется уже всего

совместимых векторов).
Т.е., считая вектора вершинами графа, а совместимость - ребрами, можно свести решение задачи к решению задачи о k-клике (для

).
Обратное сведение у меня получается. Есть у кого-то дальнейшие идеи?