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
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
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
In other words, if and only if the matrix is a permutation matrix.