1
$\begingroup$

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

  • 0
    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 ;-).2012-07-27

1 Answers 1

10

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.