Communications Toolbox

Linear Algebra in Galois Fields

You can do linear algebra in a Galois field using Galois arrays. Important categories of computations are inverting matrices, computing determinants, computing ranks, factoring square matrices, and 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.
  

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]
  
  ans =
  
       2     3
  

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

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
  

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.

	Backslash Operator (\)	Slash Operator (/)
Linear Equation	A * x = B	x * A = B
Syntax	x = A \ B	x = B / A
Equivalent Syntax Using \	Not applicable	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, then the output x is the unique solution to the linear equation.
• If A is square and singular, then the syntax in the table produces an error.
• If A is not square, then 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, then 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).

Matrix Manipulation in Galois Fields

Signal Processing Operations in Galois Fields