Learn more about Communications Toolbox

Linear Algebra in Galois Fields

On this page…
Inverting Matrices and Computing Determinants Computing Ranks Factoring Square Matrices Solving Linear Equations

Inverting Matrices and Computing Determinants

To invert a square Galois array, use the inv function. Related is the det function, which computes the determinant of a Galois array. Both inv and det behave like their ordinary MATLAB counterparts, except that they perform computations in the Galois field instead of in the field of complex numbers.

Note   A Galois array is singular if and only if its determinant is exactly zero. It is not necessary to consider roundoff errors, as in the case of real and complex arrays.

The code below illustrates matrix inversion and determinant computation.

m = 4;
randommatrix = gf(randint(4,4,2^m),m);
gfid = gf(eye(4),m);
if det(randommatrix) ~= 0
    invmatrix = inv(randommatrix);
    check1 = invmatrix * randommatrix;
    check2 = randommatrix * invmatrix;
    if (isequal(check1,gfid) & isequal(check2,gfid))
        disp('inv found the correct matrix inverse.');
    end
else
    disp('The matrix is not invertible.');
end

The output from this example is either of these two messages, depending on whether the randomly generated matrix is nonsingular or singular.

inv found the correct matrix inverse.
The matrix is not invertible.

Back to Top

Computing Ranks

To compute the rank of a Galois array, use the rank function. It behaves like the ordinary MATLAB rank function when given exactly one input argument. The example below illustrates how to find the rank of square and nonsquare Galois arrays.

m = 3;
asquare = gf([4 7 6; 4 6 5; 0 6 1],m);
r1 = rank(asquare);
anonsquare = gf([4 7 6 3; 4 6 5 1; 0 6 1 1],m);
r2 = rank(anonsquare);
[r1 r2]

The output is

ans =

     2     3

The values of r1 and r2 indicate that asquare has less than full rank but that anonsquare has full rank.

Back to Top

Factoring Square Matrices

To express a square Galois array (or a permutation of it) as the product of a lower triangular Galois array and an upper triangular Galois array, use the lu function. This function accepts one input argument and produces exactly two or three output arguments. It behaves like the ordinary MATLAB lu function when given the same syntax. The example below illustrates how to factor using lu.

tofactor = gf([6 5 7 6; 5 6 2 5; 0 1 7 7; 1 0 5 1],3);
[L,U]=lu(tofactor); % lu with two output arguments
c1 = isequal(L*U, tofactor) % True
tofactor2 = gf([1 2 3 4;1 2 3 0;2 5 2 1; 0 5 0 0],3);
[L2,U2,P] = lu(tofactor2); % lu with three output arguments
c2 = isequal(L2*U2, P*tofactor2) % True

Back to Top

Solving Linear Equations

To find a particular solution of a linear equation in a Galois field, use the \ or / operator on Galois arrays. The table below indicates the equation that each operator addresses, assuming that A and B are previously defined Galois arrays.

Operator	Linear Equation	Syntax	Equivalent Syntax Using \
Backslash (\)	A * x = B	x = A \ B	Not applicable
Slash (/)	x * A = B	x = B / A	x = (A'\B')'

The results of the syntax in the table depend on characteristics of the Galois array A:

• If A is square and nonsingular, the output x is the unique solution to the linear equation.

• If A is square and singular, the syntax in the table produces an error.

• If A is not square, MATLAB attempts to find a particular solution. If A'*A or A*A' is a singular array, or if A is a tall matrix that represents an overdetermined system, the attempt might fail.

Note   An error message does not necessarily indicate that the linear equation has no solution. You might be able to find a solution by rephrasing the problem. For example, gf([1 2; 0 0],3) \ gf([1; 0],3) produces an error but the mathematically equivalent gf([1 2],3) \ gf([1],3) does not. The first syntax fails because gf([1 2; 0 0],3) is a singular square matrix.

Example: Solving Linear Equations

The examples below illustrate how to find particular solutions of linear equations over a Galois field.

m = 4;
A = gf(magic(3),m); % Square nonsingular matrix
Awide=[A, 2*A(:,3)]; % 3-by-4 matrix with redundancy on the right
Atall = Awide'; % 4-by-3 matrix with redundancy at the bottom
B = gf([0:2]',m);
C = [B; 2*B(3)];
D = [B; B(3)+1];
thesolution = A \ B; % Solution of A * x = B
thesolution2 = B' / A; % Solution of x * A = B'
ck1 = all(A * thesolution == B) % Check validity of solutions.
ck2 = all(thesolution2 * A == B')
% Awide * x = B has infinitely many solutions. Find one.
onesolution = Awide \ B;
ck3 = all(Awide * onesolution == B) % Check validity of solution.
% Atall * x = C has a solution.
asolution = Atall \ C;
ck4 = all(Atall * asolution == C) % Check validity of solution.
% Atall * x = D has no solution.
notasolution = Atall \ D;
ck5 = all(Atall * notasolution == D) % It is not a valid solution.

The output from this example indicates that the validity checks are all true (1), except for ck5, which is false (0).

Back to Top

Matrix Manipulation in Galois Fields

Signal Processing Operations in Galois Fields

© 1984-2009- The MathWorks, Inc.    -   Site Help   -   Patents   -   Trademarks   -   Privacy Policy   -   Preventing Piracy   -   RSS