How to determine the value of a matrix?

If , where A is integer matrix, Wis integer matrix and F is integer matrix.

If I know the value of F ( integer matrix)

F = [1     1     0     1 ; 0    -1    -1     1] % 2*4 integer matrix

How to determine the value of matrices A and W

subject to:

1. In W matrix, the values of elements w13, w14, w21, w22 = zero, i.e.,

W = [w11 w12 0 0; 0 0 w23 w24]; 

2. Also, w11, w12, w23, w24 are integers.

3. All values of matrix A are also integers.

Answer 1

[Thiago Henrique Gomes Lobato]

What you have is an integer matrix factorization problem, which is a rather complex topic. Main points that you have to take in account for your problem is that:

1. There are, in most cases, infinite solutions (or results with same error) with different A and W combinations, so ideally you should have a kind of regularization to handle what you expect as the results.
2. It can also be the case that the factorization is not perfect due to lack of degree of freedoms.

Taking this in consideration there are some approaches you can try to solve the problem. The first one is almost a "brute force", where you simply optimize all variables with an integer optimizer:

rng(11)
F = [1     1     0     1 ; 0    -1    -1     1];
ub = ones(1,8)*2;
lb = -ones(1,8)*2;

fun = @(x,F) norm( [x(1),x(2);x(3),x(4)]*[x(5),x(6),0,0;0,0,x(7),x(8)]-F  );
[x,fval] = ga(@(x)fun(x,F),8,[],[],[],[],lb,ub,[],[1:8]); % Genetic algorithm with integer constrain
A = [x(1),x(2);x(3),x(4)]
W = [x(5),x(6),0,0;0,0,x(7),x(8)]
Frec = A*W
fval

A =

     1     0
     0    -1


W =

     1     1     0     0
     0     0     1    -1


Frec =

     1     1     0     0
     0     0    -1     1


fval =

     1

You see that even with a brute force method F is still not entirely reconstructed, but the norm of the error is relatively low. Another approach you could use is to solve for the matrix iteractively (for a given A, solve for W, then use W to solve for A, etc), although the correctness of the results may strongely depend on your initial guess:

F = [1     1     0     1 ; 0    -1    -1     1];
W = [1 1 0 0; 0 0 1 1];
for idx=1:3
A =  ( F*pinv(W) );
A =  ceil(abs(A)).*sign(A); % force an integer value
Wtemp =  ( pinv(A)*F );
Wtemp = ceil(abs(Wtemp)).*sign(Wtemp);
W(1,1:2)=Wtemp(1,1:2);W(2,3:4)=Wtemp(2,3:4);
end
A
W
Frec = A*W
fval = norm(A*W-F)

A =

     1     1
    -1     1


W =

     1     1     0     0
     0     0    -1     1


Frec =

     1     1    -1     1
    -1    -1    -1     1


fval =

     1

You see that the error is the same even though the matrices and optimization approach are different, which means that this error is probably a lower bound in your problem.

[Adi Nor]

Thanks for your answer.

If I want to minimize the error in your code (fval = 0), what should I do?

[Adi Nor]

I try to limit the search direction, what if I add additional constraints as:

are integers and not equal to zeros. Also, the rank of matrix A must be 2.

How can I add these constraints to your proposed code in order to limit the search direction?