Find an efficient algorithm for a matrix operation

Question

This is an interview question:

For a matrix, we define an operation that when we add 1 to one entry, all the surrounding entries (up, down, left, right) will also added by 1. Given a positive matrix, find an algorithm to determine if the matrix can be constructed from zero matrix using such operation.

What is an efficient algorithm to solve the question?

What I can currently think of is to use backtracking to try every possible combinations, however this is definitely not efficient. The question is sort of like Lights Off game, but it is not 0/1 here which makes more complicated.

Thanks.

Edit:

For example:

3 3 can be constructed from 0 0 -> 1 1 -> 2 2 -> 3 3
1 2                         0 0    1 0    1 1    1 2

Answer 1

Linear algebra?

Cell i,j is touched x<sub>ij</sub> times.

n² variables and equations. Solve. O(n^6) by Gaussian method, other faster methods might exists.

Also, matrix is special so might be able to make it faster.