Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

My question is bit more mathematical then algorithmic.

Let's say I have 4x4 natural numbers matrix (including 0), is there any inverted matrix which also contains only natural numbers to it?

Thanks for any help give. Shahar

share|improve this question

migrated from mathematica.stackexchange.com Jul 27 '12 at 12:12

This question came from our site for users of Mathematica.

    
You could try on math.stackexchange. –  assylias Jul 27 '12 at 11:47
    
Most natural number matrices either are not invertible or have an inverse containing negative numbers or fractions. The identity matrix however contains only natural numbers and zeros, and so does its inverse ;-). –  Don Roby Jul 27 '12 at 11:49
add comment

1 Answer 1

Let us first consider the case of integer matrices. A square integer matrix A has an inverse with rational entries if and only if det(A) != 0. The entries of the inverse are all integers if and only if the determinant det(A) == ±1.

Now, for matrices with natural numbers as entries, each product (entry of A)*(entry of B) is a natural number and the entries of the product are sums of natural numbers. So they can be 0 only if all of the contributing products of entries are 0, and 1 only if all the contributing products of entries but one are zero, and the nonzero product is 1.

Thus a matrix with natural numbers as entries has an inverse with natural entries if and only if

  • each row contains exactly one 1 and only 0 otherwise
  • each column contains exactly one 1 and only 0 otherwise

In other words, if and only if the matrix is a permutation matrix.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.