2
$\begingroup$

How to prove that if $A$ and $B$ are two $n×n$ matrices with non negative integer entries such that $AB=I$.Then how to show $A$ and $B$ are permutation matrices.Permutation matrices are matrices with the columns just a permutation of the identity matrix. How do i proceed.Can somebody hint.

$\endgroup$
3
$\begingroup$

Hint : Which pairs of vectors with non-negative integers have scalar-product $0$ or $1$ ?

$\endgroup$
  • $\begingroup$ Additional hint : Use $A^TB^T=(BA)^T=I^T=I$ and the row-sum-norm $\endgroup$ – Peter Feb 11 '17 at 18:36
  • 1
    $\begingroup$ i can see that if any of the entries in $A$ is greater than $1$ then since the product with entries from B has to result in a $0$ or $1$ then that column of B has to be zero which contradicts the invertibility of B $\endgroup$ – Upstart Feb 11 '17 at 18:46
  • $\begingroup$ Excellent. Now rule out that we have more than one $1$ in any column or row. Finally rule out a zero-row/zero-column (almost trivial) $\endgroup$ – Peter Feb 11 '17 at 18:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.