You can't use LU anyway, since it is not designed to work on that problem. Nor can you use slash or backslash, which again, do not understand arithmetic mod anything. So you can't use the built-in tools to do this.
I may have posted a code I called rrefgf on the FEX. The idea is that the basic linear algebra tools CAN be written to work in the multiplicative group of integers modulo some number. And when I say can be written, one would need to write them, as I did with rrefgf.
It all works well enough when the modulus is prime, because then everything has a multiplicative inverse. (Well, not zero, but that is irrelevant.) But when you are working mod p^m, things get a little harder.
I also posted a tool called modinv, It, or something equivalent, is necessary when working on problems like this. (modinv was easily written using gcd in MATLAB.) For example, if I do this:
modinv(2:24,25)
ans =
Columns 1 through 16
13 17 19 NaN 21 18 22 14 NaN 16 23 2 9 NaN 11 3
Columns 17 through 23
7 4 NaN 6 8 12 24
As you can see, 5,10,15,20 all lack a multiplicative inverse, when treated in the mutiplicative group of integers mod 25. And that makes it all much more difficult.
However, nothing is impossible. For example, we might do this:
P = 25;
Aprob = magic(5);
X0 = randi(24,[5,1])
b = mod(Aprob*X0,P)
So we know a solution does exist, because I created b from a known solution. (Aprob should be rank deficient in that field however.) Now solve the problem, at least for a particular solution. GA can probably handle it, as long as I give it some leeway.
obj = @(X) sum((mod(Aprob*X(:),P) - b).^2);
intcon = 1:5;
LB = zeros(5,1);
UB = (P-1)*ones(5,1);
opts = optimoptions('ga',maxgenerations = 100000,populationsize = 200);
[Xga,fval,exitflag] = ga(obj,5,[],[],[],[],LB,UB,[],intcon,opts)
A different solution, but equally good, since this problem lacks a unique solution. I could also have used intlinprog on the same problem, and not have worried so much about convergence, as might be an issue with GA.
f = [zeros(5,1);ones(5,1)]; % introucing slack variables to handle mod.
Ai = [Aprob,25*eye(5)];
LB = [zeros(5,1);-inf*ones(5,1)];
UB = [24*ones(5,1);inf*ones(5,1)];
intcon = 1:10;
[Xi,fval,exitflag] = intlinprog(f,intcon,[],[],Ai,b,LB,UB)
How well did it do?
Xi = round(Xi(1:5)); % The round makes sure Xi is all truly integer
mod(Aprob*Xi - b,P)
As you can see, intlinprog also works, although the solution is again different. There is no expectation it will find the same solution as anything else on a rank deficient problem. Do you really want the fully general solution? That can probably be done too, possibly using my rrefgf code, or something like it.
