Теоретический материал

Некоторые обозначения и определения

Матрицей размера n×m называется прямоугольная таблица n×m, составленная из чисел.

Обычно матрицы обозначают заглавными латинскими буквами. Элемент i-й строки j-го столбца матрицы A обозначают через a_ij или a[i, j] (соответствующая маленькая латинская буква с индексами).

Произведением двух матриц ${A \atop n \times m}$ и ${B \atop m \times k}$ называется матрица такая ${C \atop n \times k}$ , что

c_ij = $\displaystyle \sum_{t = 1}^{m}$ a_itb_tj.

(1)

В этом случае пишут: C = AB.

D в степени k (D^k), при условии, что D -- квадратная (т. е. n = m) определяется следующим образом:

D⁰ = E (единичная матрица), где

E = $\displaystyle \left(\vphantom{\begin{array}{ccccccccc} 1 & 0 & 0 & \ldots & 0 \... ...dots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \ldots & 1 \end{array}}\right.$ $\displaystyle \begin{array}{ccccccccc} 1 & 0 & 0 & \ldots & 0 \\ 0 & 1 & 0 & ... ...ots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \ldots & 1 \end{array}$ $\displaystyle \left.\vphantom{\begin{array}{ccccccccc} 1 & 0 & 0 & \ldots & 0 \... ...dots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \ldots & 1 \end{array}}\right)$ .
На диагонали у нее стоят единицы, в остальных клетках -- нули. Она не зря называется единичной -- при умножении на нее матрица не изменяется: AE = EA = A.
Dⁱ = D^{i - 1}D, i > 0.

В приводимом коде будет использоваться функция bit(x,i), возвращающая единицу или ноль -- i-й бит в двоичной записи числа x (нумерация битов с нуля).

// возвращает i-й бит числа x, нумерация с нуля
function bit(x, i : integer) : integer;
begin
    if (i < 0) then bit := 0 else
        if (x and (1 shl i) = 0) then bit := 0 else bit := 1;
end;