QR Factorization mod2

I need to find the QR factorization of a matrix A but with the rule that 1+1=0. This is where mod2 comes in; I figured it would work well to maintain this rule, but can't figure out the code for it. Can I just manipulate the built in QR factorization function?

[Q,R] = qr(A)

Thanks!

Answer 1

[Balavignesh]

Hi Eve,

Manipulating the built-in QR factorization function in MATLAB to work under arithmetic modulo 2 directly is not straightforward. The QR factorization, as implemented in MATLAB ([Q,R] = qr(A)), uses floating-point arithmetic and is designed for real or complex matrices. It relies on the properties of real or complex numbers, such as division, which do not have direct analogs in arithmetic modulo 2.

Implementing QR factorization under mod2 would require a fundamentally different approach, similar to creating a custom algorithm that respects mod2 arithmetic rules. Since the QR factorization typically involves operations like the Gram-Schmidt process or Householder reflections, which in turn rely on division and square roots, translating these directly to mod2 is non-trivial and may not be meaningful in the same way as it is for real numbers.

However, for exploratory purposes, if you're interested in a kind of "binary" or "mod2" manipulation that doesn't strictly adhere to the mathematical rigor of QR factorization but rather adapts the idea to mod2, you would have to start from the basics of the algorithm you wish to use (e.g., Gram-Schmidt) and modify each step to work under mod2 rules.

The following code snippet demonstrates 'mod2' manipulation in a simplistic or vague way:

function [Q, R] = qr_mod2(A)
    % This is a highly simplified and not mathematically rigorous example
    % of how one might begin to approach the idea of QR-like factorization
    % under mod 2 arithmetic. It does not perform actual QR factorization.

    % Ensure A is in mod2
    A = mod(A, 2);

    [m, n] = size(A);
    Q = zeros(m, n);
    R = zeros(n, n);

    for j = 1:n
        % For mod2, let's just copy the column as a starting point
        Q(:, j) = A(:, j);
        for i = 1:j-1
            % Attempt to orthogonalize in mod2 (this part is not mathematically rigorous)
            R(i, j) = mod(dot(Q(:, i), A(:, j)), 2);
            Q(:, j) = mod(Q(:, j) - R(i, j) * Q(:, i), 2);
        end
        % Normalization step doesn't translate well to mod2, but we ensure binary values
        Q(:, j) = mod(Q(:, j), 2);
        R(j, j) = 1; % Simplification for illustration
    end
end

Have a look at the following documentation links to have more information on:

• 'mod' function: https://www.mathworks.com/help/matlab/ref/mod.html
• 'zeros' function: https://www.mathworks.com/help/matlab/ref/zeros.html

Happy to help!

Balavignesh