В предыдущем параграфе (см.12.7) мы отмечали, что размерностный многочлен любого множества $$F\subseteq \N^m$$ равен размерностному многочлену, ассоциированному с множеством всех минимальных элементов множества $$F$$. Значит, достаточно уметь вычислять размерностные многочлены только для конечных множеств $$F\subseteq\N^m$$ (более того, можно предполагать, что элементы множества $$F$$ попарно несравнимы относительно порядка произведения).
Пусть $$E=(e_{ij})_{\substack{1\leq i\leq n\\ 1\leq j \leq m}}$$ обозначает $$n\!\times\! m$$ -матрицу над $$\mathbb N$$, т. е. матрицу с $$n$$ строками и $$m$$ столбцами, элементы которой - неотрицательные целые числа. Рассматривая строки матрицы $$E$$ как элементы множества $$\mathbb N^m$$ и обозначая $$i$$ -ю строку $$(e_{i1},\dots,e_{im})$$ через $$e_i$$ $$(1\leq i\leq n)$$, мы получим подмножество $$\tilde E=\{e_1,\dots,e_n\} \subseteq\mathbb N^m$$, ассоциированное с $$E$$. Напомним, что размерностный многочлен $$n\!\times\! m$$ -матрицы $$E$$ в точности совпадает с размерностным многочленом множества $$\tilde E$$ и называется многочленом Гильберта матрицы $$E$$.
Пусть $$\omega_E(t)$$ - размерностный многочлен $$n\!\times\!m$$ -матрицы $$E$$ над $$\mathbb N$$. По определению $$\omega_E(s)=Card V_E(s)$$ для всех достаточно больших $$s\in\mathbb N$$, где $$V_E$$ обозначает множество всех элементов из $$\mathbb N^m\setminus \tilde E$$, которые не превосходят ни одного элемента из $$\tilde E$$ относительно порядка произведения, так что $$v\in V_E$$ если и только если неравенство $$e_i\leq v$$ не выполняется ни для одного $$e_i$$ $$(1\leq i\leq n)$$.
Как было отмечено, для того, чтобы уметь вычислять размерностный многочлен любого подмножества в $$\mathbb N^m$$, достаточно уметь вычислять его для любой $$n\!\times\! m$$ -матрицы $$E$$ над $$\mathbb N$$. Один из методов вычисления основан на формуле (12,4).
Пусть $$E=(e_{ij})_{\substack{1\leq i\leq n\\ 1\leq j \leq m}}$$ обозначает $$n\!\times\!m$$ -матрицу над $$\mathbb N$$. Воспользуемся следующими обозначениями, введенными в параграфе 12:$$\textbf{e}_\xi=\begin{cases} (0,\dots,0) \text{если } \xi=\emptyset,\\ (e_1=\max_{i\in\xi}\{ e_{i1}\} ,\dots,e_m= \max_{i\in\xi}\{ e_{im}\} ) \text{если } \xi\neq \emptyset \end{cases}$$ для любого подмножества $$\xi\subseteq\mathbb N_n$$ и $$|\textbf{e}_\xi|=\smash{\sum\limits_{j=1}^m}e_j$$. По предложению 12.9 (см. 12.4) мы можем записать$$\omega_E(t) = \binom {t+m}m +\sum_{l=1}^n(-1)^l \sum_{\xi\in A(l,n)}\binom{t+m-|\textbf{e}_\xi|}m,$$ где $$A(l,n)$$ $$(1\leq l\leq n)$$ обозначает множество всех $$l$$ -элементных подмножеств множества $$\mathbb N_n=\{1,\dots,n\}$$.
Пользуясь выписанной формулой, можно предложить следующий алгоритм вычисления размерностного многочлена $$\omega_E(t)$$, ассоциированного с $$n\!\times\! m$$ -матрицей $$E$$.
А9. АЛГОРИТМ $$(E, n, m, \omega)$$.
$$ \text{Дано: $n \in \mathbb N ; m \in \mathbb N ; n \times m$-матрица E}.\\ \text{Надо: $\omega_E(t)$ — многочлен Гильберта матрицы $E$.}\\ \text{Переменные: $IB$ — вектор типа $true/false$ с индексами $1..n$;}\\ \text{\qquad \qquad $\textbf{v} = (v1, . . . , vm)$ — вектор типа $N$ с индексами $1..m$;}\\ \text{\qquad \qquad $S_1$ — переменная типа $\pm 1$;}\\ \text{\qquad \qquad $S_2$ — переменная типа $ \mathbb N $.}\\ \text{Начало}\\ \text{$\omega(t) := \binom {t+m}m$}\\ \text{цикл для $m$ каждого вектора $IB$}\\ \text{\qquad $v := (0, . . . , 0)$}\\ \text{\qquad $S_1 := 1$}\\ \text{\qquad цикл для $j$ от $1$ до $n$}\\ \text{\qquad \qquad если $IB(j)$ то}\\ \text{\qquad \qquad \qquad $\textbf{v} := НОК(\textbf{v}, \textbf{e}_j)$}\\ \text{\qquad \qquad \qquad $S_1 := -S_1$}\\ \text{\qquad \qquad конец если}\\ \text{\qquad \qquad $S_2 := \textbf{v}_1 + \dots + \textbf{v}_m$}\\ \text{\qquad \qquad $\omega(t) := \omega(t) + S_1\binom {t+m-S_2}m$}\\ \text{\qquad конец цикла} \\ \text{конец цикла}\\ \text{Конец}\\ $$Легко видеть, что асимптотическая сложность алгоритма A9 имеет порядок $$n\!\times\! 2^n$$, где $$n$$ - число строк матрицы $$E$$ (по теореме 12.8 мы можем считать, что строки попарно несравнимы относительно порядка произведения на $$\mathbb N^m$$ ).
Мора и Меллер модифицировали алгоритм вычисления многочлена Гильберта . Их алгоритм основан на следующих соображениях. Легко видеть, что в формуле (12.5) может выполняться равенство $$\textbf{e}_\xi=\textbf{e}_\theta$$ для двух различных подмножеств $$\xi$$ и $$\theta$$ множества $$\mathbb N_n$$, таких, что $$Card\xi$$ и $$Card\theta$$ являются четным и нечетным числами соответственно (мы пользуемся обозначениями предложения 12.9). Тогда соответствующие слагаемые в формуле (12.5) сократятся. Более того, можно сгруппировать все слагаемые, соответствующие одному и тому же элементу $$\tau \in\mathbb N^m$$.
Пусть $$T=T(E)$$ - множество всех элементов $$\tau\in\mathbb N^m$$, которые равны, по крайней мере, одному из элементов $$\textbf{e}_\xi$$, где $$\xi\subseteq\mathbb N_n$$. Тогда из формулы (12.4) следует, что$$ \omega_E(t) =\sum_{\tau\in T}\sum_{k=0}^n(-1)^k\sum_{\{\xi\in A(k,n)\mid \textbf{e}_\xi=\tau\} } \binom {t+m-|\tau|}m\\ =\sum_{\tau\in T} \mu_\tau \binom {t+m-|\tau|}m,\ $$ где $$|\tau|$$ обозначает сумму всех координат вектора $$\tau$$, и$$\begin{equation} \mu_\tau=\sum\limits_{k=0}^n\sum\limits_{\substack{ \xi\in A(k,n)\\\textbf{e}_\xi=\tau} }(-1)^k. \end{equation}$$
Очевидно, если матрица $$E_1$$ получена присоединением строки $$\textbf{e} = (e_1,\dots,e_m)$$ к матрице $$E$$, $$T_1= T(E_1)$$ и $$\{\mu'_\tau|\tau \in T_1\}$$ - множество коэффициентов (13.2) в соотношении (13.1) для многочлена $$\omega_{E_1}(t)$$, так что$$\mu'_\tau= \sum_{k=0}^{n+1}\sum_{\substack{ \xi\in A(k,n+1)\\\textbf{e}_\xi=\tau} }(-1)^k$$ для каждого $$\tau \in T_1$$, то$$\begin{equation} \mu'_\tau=\begin{cases} \mu_\tau-\sum_{\{ u\in T\mid HOK (u,\textbf{e})=\tau\} }\mu_{u} \text{ если } \tau\in T\\ -\sum_{\{ u\in T\mid HOK (u,\textbf{e})=\tau\} }\mu_{u} \text { если } \tau\in T_1\setminus T \end{cases} \end{equation}$$
Таким образом, вычисление многочлена $$\omega_E(t)$$, т. е. вычисление коэффициентов $$\mu_\tau\ (\tau \in T)$$, в (13.1) может быть основано на формуле (13.3), если мы начнем с пустой матрицы (число строк которой равно нулю и многочлен Гильберта которой равен $$\binom {t+m}m$$ ) и последовательно будем присоединять строки матрицы $$E$$, вычисляя множество $$T$$ и коэффициенты $$\mu_\tau$$ $$(\tau \in T)$$ на каждом шаге (см. алгоритм A10 ).
$$ \text{Дано: $n \in \mathbb N ; n \times m$-матрица E}.\\ \text{Надо: $\omega_E(t)$ — многочлен Гильберта матрицы $E$.}\\ \text{Переменные: $T,\; T_1$ —множества типа}\\ \text{\qquad \qquad \qquad \qquad $\{$вектор типа $ \mathbb N $ с индексами $1..m\}$};\\ \text{\qquad \qquad \qquad $\mu, \mu_1$ —векторы типа $ \mathbb Z $ с индексами из $T, T_1$.}\\ \text{Начало}\\ \text{$\omega:= 0$}\\ \text{$T:=\{(0, \dots , 0)\}$}\\ \text{$\mu (0, \dots , 0):=1$}\\ \text{цикл для $i$ от $1$ до $n$}\\ \text{\qquad $T_1:=T$}\\ \text{\qquad цикл для каждого $u \in T_1$}\\ \text{\qquad \qquad $\mu_1(\textbf{u}):=\mu(\textbf{u})$}\\ \text{\qquad конец цикла}\\ \text{\qquad цикл для каждого $u \in T_1$}\\ \text{\qquad \qquad $\tau := НОК(\textbf{u}, ei), e_i —i$-я строка матрицы $E$}\\ \text{\qquad \qquad если $\tau \in T$ то}\\ \text{\qquad \qquad \qquad $\mu(\tau ) := \mu(\tau ) - \mu_1(\textbf{u})$}\\ \text{\qquad \qquad иначе $T := T \cup \tau ; \mu(\tau ) := -\mu_1(\textbf{u})$}\\ \text{\qquad \qquad конец если}\\ \text{\qquad конец цикла}\\ \text{конец цикла}\\ \text{цикл для каждого $\textbf{u} \in T$}\\ \text{\qquad $\omega (t):= \omega (t) + \mu(\textbf{u})\binom {t+m-|\textbf{u}|}m$}\\ \text{конец цикла}\\ \text{Конец}\\ $$Поскольку на $$k$$ -м шаге $$(1\leq k\leq n)$$ алгоритма каждый элемент $$\textbf{u} \in T_1$$ является наименьшим общим кратным некоторого подмножества множества $$\{\textbf{e}_1,\dots,\textbf{e}_{k-1}\}$$ (т. е. $$\textbf{u}=\textbf{e}_\xi$$ для некоторого $$\xi\subseteq \mathbb N_{k-1}$$ ), существует не более $$(k-1)$$ различных возможностей для выбора каждой координаты вектора $$\textbf{u}$$, следовательно, на $$k$$ -м шаге $$(1\leq k\leq n)$$ множество $$T_1$$ содержит не более $$(k-1)^m$$ элементов. Вычисление всех элементов $$\tau=HOK(\textbf{u},\textbf{e}_k)$$ требует не более $$m(k-1)^m$$ сравнений, и можно предполагать (используя достаточно эффективный метод сортировки), что число проверок на принадлежность $$\tau\in T$$ не превосходит $$k^m\log k$$ для всех достаточно больших $$k \in \mathbb N$$. Таким образом, асимптотическая сложность (по $$n$$ ) алгоритма A10 не превосходит $$m\sum\limits_{k=2}^n\left[(k-1)^m+k^m\log k\right]$$. Поскольку $$m \sum\limits_{k=2}^n\left[ (k - 1)^m+ k^m\log k\right] < 2m \sum\limits_{k=2}^n k^m \log k$$, асимптотическая сложность имеет порядок $$n^{m+1}\log n$$.
Следующие алгоритмы вычисления размерностного многочлена произвольной $$n\!\times\! m$$ -матрицы $$E$$ сводят эту задачу к аналогичной задаче для матрицы с числом строк меньшим, чем в $$E$$. По одному из этих алгоритмов (см. ниже алгоритм A11 ) можно вычислить коэффициенты $$\mu_\tau$$ в (13.1) размерностного многочлена $$\omega_E(t)$$, что дает выражение для размерностного многочлена. Для обоснования этого алгоритма нам нужны некоторые свойства коэффициентов $$\mu_\tau$$, которые сформулированы ниже в леммах 13.1-13.5, 13.7 и 13,9. Последняя из этих лемм устанавливает соотношения, на которых основан алгоритм вычисления $$\mu_\tau$$.
Чтобы подчеркнуть зависимость коэффициентов $$\mu_\tau$$ от матрицы $$E$$, будем обозначать эти коэффициенты $$\mu_\tau (E)$$ и продолжим это обозначение на случай произвольного вектора $$\tau \in \mathbb N^m$$, полагая$$\mu_\tau(E) =\begin{cases} \mu_\tau, \text {если } \tau\in T\\ 0, \text {если } \tau\in\mathbb N^m\setminus T.\end{cases}$$ (Напомним, что $$T=T(E)$$ - множество всех элементов $$\tau\in\mathbb N^m$$, таких, что каждый $$\tau$$ равен либо $$(0,\dots,0)$$, либо наименьшему общему кратному некоторых строк матрицы $$E$$ ; элементы множества $$T$$ будем называть допустимыми элементами или допустимыми векторами матрицы $$E$$.)
13.1. ЛЕММА. Пусть дана $$n\!\times\! m$$ -матрица$$E = (e_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}.$$ Предположим, что элемент $$\tau =(\tau_1,\dots,\tau_m) \in \mathbb N^m$$ мажорирует все строки этой матрицы, т. е. $$\tau$$ больше любой строки матрицы $$E$$ или равен ей (относительно порядка произведений на $$\mathbb N^m$$ ). Тогда $$\mu_\tau(E) = \mu_{(1,\dots,1)}(H)$$, где $$H = (h_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$$ - матрица с элементами$$h_{ij}=\begin{cases} 1, \text {если } e_{ij}=\tau_j,\\ 0, \text {если } e_{ij}\neq \tau_j,\end{cases}$$ $$(i=1,\dots,n)$$.
ДОКАЗАТЕЛЬСТВО. Пусть $$\xi=\{ i_1,\dots,i_k\}\in A(k, n)$$ $$(1\leq k\leq n)$$, $$\textbf{e}_\xi=НОК \{\textbf{e}_{i_1},\dots,\textbf{e}_{i_k}\}$$ и $$\textbf{h}_\xi =НОК \{\textbf{h}_{i_1},\dots,\textbf{h}_{i_k}\}$$ ( $$\textbf{e}_i$$ и $$\textbf{h}_i$$ обозначают $$i$$ -е строки матриц $$E$$ и $$H$$ соответственно). Покажем, что равенство $$\textbf{e}_\xi=\tau$$ эквивалентно равенству $$\textbf{h}_\xi=(1,\dots,1)$$. Действительно, если $$\textbf{e}_\xi = \tau$$, то $$\tau_j= \max \{ e_{i_1j},\dots,e_{i_kj}\}$$ $$(1\leq j\leq m)$$, так что для каждого $$j=1,\dots,m$$ существует индекс $$\lambda (j)\in\mathbb N_k$$, такой, что $$h_{i_{\lambda (j)}}=1$$. Таким образом, $$j$$ -й элемент строки $$\textbf{h}_{i_{\lambda (j)}}$$ равен 1, следовательно, $$\textbf{h}_\xi =НОК \{\textbf{h}_{i_1},\dots,\textbf{h}_{i_k}\} = (1,\dots,1)$$. Обратно, если $$\textbf{h}_\xi= (1,\dots,1)$$, то для каждого $$j=1,\dots,m$$ существует число $$\nu =\nu(j)\in\mathbb N_k$$, такое, что $$h_{i_\nu j}=\max_{i\in\xi}\{ h_{ij}\} = 1$$, т. е. $$e_{i_\nu j} = \tau_j$$. Поэтому, $$\textbf{e}_\xi\geq\tau$$, следовательно, $$\textbf{e}_\xi= \tau$$ (так как элемент $$\tau$$ больше любой строки матрицы $$E$$ или равен ей). Таким образом,$$\mu_\tau =\sum\limits_{k=0}^n\sum\limits_{\substack{ \xi\in A(k,n)\\ \textbf{e}_\xi=\tau}} (-1)^k= \sum\limits_{k=0}^n\sum\limits_{\substack{ \xi\in A(k,n)\\ \textbf{h}_\xi=(1,\dots,1)}} (-1)^k=\mu_{(1,\dots,1)}(H). \eqno{\text{\qedsymbol}}$$
Рассмотрим свойства размерностных многочленов матриц, состоящих из 0 и 1
(такова, например, матрица $$H$$ в лемме
13.1). Длякраткости будем писать $$\mu_1(E)$$
вместо $$\mu_{(1,\dots,1)}(E)$$, где $$E$$ - $$n\!\times\! m$$ -матрица и $$(1,\dots,1) \in \mathbb N^m$$.
13.2. ЛЕММА. Пусть $$E$$ - $$n\!\times\! m$$ -матрица, состоящая из 0 и 1, и $$\omega_E(t)$$ - ее многочлен Гильберта. Тогда $$\mu_1(E) = (-1)^m\omega_E(-1)$$.
ДОКАЗАТЕЛЬСТВО.
По (12.4) имеем$$\begin{equation} \omega_E(t) =\sum_{\tau\in T}\mu_\tau\binom {t+m-|\tau|}m,
\end{equation}$$
и, очевидно, каждая координата любого вектора$$\tau =
(\tau_1,\dots,\tau_m) \in T=T(E)$$
равна либо 0, либо 1. Если $$\tau \neq (1,\dots,1)$$, то $$0 \leq
|\tau|= \sum\limits_{i=1}^m\tau_i < m$$. В этом случае
многочлен $$\binom {t+m-|\tau|}m$$ обращается в нуль при $$t=-1$$, следовательно,$$\begin{align*}
\omega_E(-1) = \mu_1(E)\left. \binom {t+m-|\tau|}m\right|_{t=-1} \\
= \mu_1(E)\left. \frac {t(t-1)\dots(t-m+1)}{m!}
\right|_{t=-1} \\
=(-1)^m \mu_1(E). \tag*{\qedsymbol}
\end{align*}$$
Из леммы 13.2 следует, что$$\begin{equation} \mu_1(E) = (-1)^m \omega_E(-1), \end{equation}$$ где $$\omega_E(t)$$ - многочлен Гильберта матрицы $$E$$. Если$$\omega_E(t)=\sum\limits_{i=0}^m a_i\binom {t+i}i \quad (a_0,a_1,\dots,a_m \in \mathbb Z),$$ то $$\omega_E(-1)=a_0$$, так что $$\mu_1(E)$$ равно свободному члену многочлена Гильберта $$\omega_E(t)$$.
13.3. ЛЕММА. Пусть $$E$$ - $$n\!\times\! m$$ -матрица, состоящая из 0 и 1. Тогда
ДОКАЗАТЕЛЬСТВО. Все утверждения леммы следуют из (13.5) и из доказанных выше свойств размерностного многочлена матрицы $$E$$.
(1) Если $$E$$ содержит нулевую строку, то $$\omega_E(t)\equiv 0$$ (см. теорему 12.8(6). Применяя лемму 13.2, получаем $$\mu_1(E)=0$$.
(2) Если каждый элемент $$\nu$$ -го столбца матрицы $$E$$ равен нулю $$(1\leq \nu \leq m)$$, то из формулы (13.2) следует, что $$\mu_1(E)=0$$ (действительно, в обозначениях формулы (13.2) $$\nu$$ -ая координата любого вектора $$\textbf{e}_\xi$$ $$(\xi \subseteq \mathbb N_m)$$ равна нулю, так что $$\textbf{e}_\xi\neq (1,\dots,1)$$ ни для какого подмножества $$\xi \subseteq \mathbb N_m$$ ).
(3) Очевидно, что перестановка строк (или столбцов) матрицы $$E$$ не меняет значения $$\omega_E(t)$$, а, значит, и значения $$\mu_1(E)= (-1)^m \omega_E(-1)$$ (см. утверждения (3) и (4) теоремы 12.8).
(4) Пусть $$E$$ состоит из одной строки $$\textbf{e}=(1,\dots,1)$$. Поскольку$$\begin{multiline*} V_{\textbf{e}}(s)=Card\mathbb N^m(s)\\ -Card\{(1+u_1,\dots,1+u_m)\mid (u_1,\dots,u_m) \in\mathbb N^m(s - m)\} \\ = \binom {s+m}m-\binom sm \end{multiline*}$$ для всех достаточно больших $$s\in\mathbb N$$, имеем$$\omega_E(t) = \binom {t+m}m-\binom tm = \frac {(t+1)\dots(t+m)}{m!} - \frac {t(t-1)\dots(t-m+1)}{m!}.$$ Значит, $$\mu_1(E) = (-1)^m\omega_E(-1) = (-1)^m(-1)^{m+1}= -1$$.
(5) По теореме 12.8(8) имеем $$\omega_E(t) \equiv \omega_H(t)$$, следовательно, $$\mu_1(E) =(-1)^m\omega_E(-1) = -(-1)^{m-1}\omega_H(-1) = -\mu_1(H)$$.
Пусть $$E = (e_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$$ - $$n\!\times\! m$$ -матрица над $$\mathbb N$$, $$\tilde E=\{\textbf{e}_1,\dots,\textbf{e}_n\}$$ - множество строк матрицы $$E$$ и $$\textbf{e}=(e_1,\dots,e_m)$$ - элемент множества $$\mathbb N^m$$. Пусть $$E\cup\textbf{e}$$ обозначает $$(n+1)\!\times\! m$$ -матрицу, полученную присоединением строки $$\textbf{e}$$ к матрице $$E$$ (без потери общности можно предполагать, что $$\textbf{e}$$ является $$(n+1)$$ -й строкой матрицы $$E\cup\textbf{e}$$ ). Следующая лемма устанавливает связь между размерностными многочленами матриц $$E$$ и $$E\cup\textbf{e}$$. Как и выше, $$|E|$$ обозначает сумму $$\sum\limits_{i=1}^n\sum\limits_{j=1}^me_{ij}$$ всех элементов матрицы $$E$$ (в частности, $$|\textbf{e}|$$ обозначает сумму всех координат элемента $$\textbf{e}\in\mathbb N^m$$ ).
13.4. ЛЕММА. Пусть $$E$$ является $$n\!\times\! m$$ -матрицей $$(n,m\in\mathbb N$$ ; $$m>1$$, $$n\geq 1)$$, состоящей из нулей и единиц. Если первый столбец матрицы $$E$$ состоит только из нулей, а матрица $$E_1$$ получена из $$E$$ удалением этого нулевого столбца, то $$\omega_E(-2)=-\omega_{E_1}(-1)$$.
ДОКАЗАТЕЛЬСТВО. Применяя формулу (12.2) к матрице $$E$$ и вектору $$\textbf{e}=(1,0,\dots,0)$$, получим $$\omega_E(t) = \omega_{E\cup\textbf{e}}(t) + \omega_H(t-1)$$, где $$H = (h_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$$ - матрица с элементами $$h_{ij}=\max \{e_{ij}- e_j,0\}$$ ( $$e_1= 1,\ e_2=0,\dots,e_m= 0$$ суть координаты вектора $$\textbf{e}$$ ). Очевидно, $$H=E$$ и $$\omega_{E\cup\textbf{e}}(t) =\omega_{E_1}(t)$$ (см. теорему 12.8(8)), так что $$\omega_E(t)= \omega_{E_1}(t)+\omega_E(t-1)$$ и, в частности, $$\omega_{E_1}(-1) + \omega_E(-2) = \omega_E(-1)$$. Поскольку $$E$$ содержит нулевой столбец, из леммы 13.3(2) следует, что $$\omega_E(-1) = (-1)^m\mu_1(E) = 0$$, значит, $$\omega_E(-2) = -\omega_{E_1}(-1)$$.
13.5. ЛЕММА. Пусть $$E = (e_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$$ $$(n,m\in\mathbb N$$ ; $$m>1$$, $$n\geq 1)$$ является $$n\!\times\! m$$ -матрицей состоящей из нулей и единиц. Предположим, что $$e_{j1}=1$$ для $$j=1,\dots,r$$ и $$e_{j1}=0$$ для $$j=r+1,\dots,n$$ $$(1\leq r\leq n)$$. Тогда $$\mu_1(E)= \mu_1(E_1) - \mu_1(E_2)$$, где матрица $$E_1$$ получена из $$E$$ удалением первого столбца, а $$E_2$$ получена из $$E_1$$ удалением $$r$$ первых строк.
ДОКАЗАТЕЛЬСТВО. Применяя (12.2) к $$E$$ и $$\textbf{e}= (1,0,\dots,0)$$, получаем $$\omega_E(t) = \omega_{E\cup \textbf{e}}(t) + \omega_H(t-1)$$, где $$H= (h_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$$ - $$n\!\times\! m$$ -матрица с элементами$$h_{ij}=\max \{ e_{ij}- e_j,0\} = \begin{cases} 0, \kern-7pt\text {если } j=1,\\ e_{ij}, \kern-7pt\text {если } j\neq 1.\end{cases}$$ По теореме 12.8(8) $$\omega_{E\cup\textbf{e}}(t) = \omega_{E_2}(t)$$, следовательно, $$\omega_E(t) = \omega_{E_2}(t) + \omega_H(t-1)$$. Далее, пользуясь леммой 13.4, можно написать $$\omega_H(-2) = -\omega_{E_1}(-1)$$, значит, $$\omega_E(-1) = \omega_{E_2}(-1) - \omega_{E_1}(-1)$$. Теперь, по лемме 13.2 имеем$$\begin{multiline*} \mu_1(E) = (-1)^m\omega_E(-1) = (-1)^m\omega_{E_2}(-1) + (-1)^{m-1}\omega_{E_1}(-1) \\ = \mu_1(E_1) - \mu_1(E_2). \tag*{\qedsymbol} \end{multiline*}$$
13.6. СЛЕДСТВИЕ. Пусть
$$E =(e_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$$ $$(m,n\in\mathbb N,\ m>1)$$ - $$n\!\times\! m$$ -матрица, состоящая из 0 и 1. Предположим, что существуют $$p,q\in\mathbb N_m$$, такие, что $$e_{ip}\geq e_{iq}$$ для всех $$i=1,\dots,n$$. Тогда $$\mu_1(E) = \mu_1(E_1)$$, где $$E_1$$ получена из $$E$$ удалением $$p$$ -го столбца.
ДОКАЗАТЕЛЬСТВО. Поскольку размерностный многочлен матрицы $$E$$ инвариантен относительно перестановок строк (или столбцов) матрицы $$E$$, значение $$\mu_1(E) = (-1)^m \omega_E(-1)$$ также обладает этим свойством. Поэтому, без потери общности, можно считать, что $$p=1$$ и существует $$r\in\mathbb N_{n-1}$$, такое, что $$e_{j1}= 1$$ для $$j = 1,\dots,r$$, и $$e_{j1}= 0$$ для $$j = r+1,\dots,n$$. По лемме 13.5, $$\mu_1(E) =\mu_1(E_1)-\mu_1(E_2)$$, где $$E_2$$ получена из $$E$$ удалением первого столбца и $$r$$ первых строк (поскольку $$0\leq e_{iq}\leq e_{i1}=0$$ для $$i=r+1,\dots,n$$, каждый элемент $$q$$ -го столбца матрицы $$E_2$$ равен нулю). Следовательно, $$\mu_1(E_2)=0$$ (см. лемму 13.3(2)), так что $$\mu_1(E)=\mu_1(E_1)$$.
13.7. ЛЕММА. Пусть
$$E =(e_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$$ $$(m,n\in\mathbb N,\ m>1)$$ - $$n\!\times\! m$$ -матрица, состоящая из 0 и 1. Предположим, чт о $$E$$ содержит строку $$\textbf{e}=(e_1,\dots,e_m)$$, такую, что $$e_i=1$$ для $$1\leq i\leq r$$ и $$e_i= 0$$ для $$r<i\leq m$$ $$(r \in \mathbb N_{m-1})$$. Тогда $$\mu_1(E) = \mu_1(E\setminus \textbf{e}) - \mu_1(E_1)$$, где матрица $$E\setminus \textbf{e}$$ получена удалением строки $$\textbf{e}$$ из матрицы $$E$$, а $$(n-1)\!\times\! (m-r)$$ - матрица $$E_1$$ получена из матрицы $$E\setminus \textbf{e}$$ удалением $$r$$ первых столбцов.
ДОКАЗАТЕЛЬСТВО. Применяя формулу (12.3) к матрице $$E$$ и строке $$\textbf{e}=(1,\dots,1,0,\dots,0)$$, получаем $$\omega_E(t) = \omega_{E\setminus \textbf{e}}(t) - \omega_{\tilde E_1}(t-r)$$, где матрица $$\tilde E_1$$ получена из $$E_1$$ присоединением слева $$r$$ нулевых столбцов. Теперь из (12.2) видно, что $$\omega_{\tilde E_1}(t) = \omega_{\tilde E_1\cup\textbf{e}}(t) + \omega_{\tilde E_1}(t-r)$$, следовательно,$$\omega_E(-1) = \omega_{E\setminus \textbf{e}}(-1) - \omega_{\tilde E_1}(-1-r) = \omega_{E\setminus \textbf{e}}(-1) + \omega_{\tilde E_1\cup\textbf{e}}(-1)-\omega_{\tilde E_1}(-1).$$
Поскольку $$\tilde E_1$$ содержит нулевой столбец, из пункта 2 леммы 13.3 следует, что $$\mu_1(\tilde E_1) = 0$$, значит,$$\omega_{\tilde E_1}(-1) = (-1)^m\mu_1(\tilde E_1) = 0$$ (см. лемму 13.2) и$$\begin{align*} \mu_1(E)= (-1)^m\omega_E(-1) = (-1)^m\omega_{E\setminus \textbf{e}}(-1) + (-1)^m \omega_{\tilde E_1\cup\textbf{e}}(-1)\\ =\mu_1(E\setminus\textbf{e})+\mu_1(\tilde E_1\cup \textbf{e}). \end{align*}$$ Поскольку каждый из первых $$(r-1)$$ столбцов матрицы $$\tilde E_1\cup \textbf{e}$$ мажорирует $$r$$ -й столбец этой матрицы, из следствия 13.6 вытекает, что $$\mu_1(\tilde E_1\cup \textbf{e})= \mu_1({\mathbf0}E_1\cup (1,0,\dots,0))$$, где $${\mathbf0}E_1$$ - матрица, полученная присоединением слева нулевого столбца к $$E_1$$. Применяя теперь п.5 леммы 13.3, получаем $$\mu_1({\mathbf0 E_1\cup(1,0,\dots,0)) =-\mu_1(E_1)$$, откуда следует требуемое соотношение $$\mu_1(E)=\mu_1(E\setminus\textbf{e})-\mu_1(E_1)$$.
Пусть
$$E = (e_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$$ - $$n\!\times\! m$$ -матрица. По теореме 12.8 п.5, удаление "лишних" строк матрицы $$E$$ не меняет размерностный многочлен этой матрицы, значит, не меняет и значение $$\mu_1(E)$$. Кроме того, если любой элемент матрицы $$E$$ равен либо 0, либо 1, то из следствия 13.6 вытекает, что удаление "лишних" столбцов матрицы $$E$$ не меняет значения $$\mu_1(E)$$ ( $$p$$ -й столбец матрицы $$E = (e_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$$ $$(1\leq p\leq m)$$ называется "лишним", если существует число $$q \in \mathbb N_m$$, такое, что $$q \neq p$$ и $$e_{ip}\geq e_{iq}$$ для всех $$i=1,\dots,n $$ ).
Таким образом, в ходе вычисления $$\mu_1(E)$$ (где $$E$$ - $$n\!\times\! m$$ -матрица, состоящая из 0 и 1) мы можем прежде всего отбросить "лишние" строки и столбцы (по п.5 леммы 13.3, эти вычисления сопровождаются соответствующими изменениями знака $$\mu_1(E)$$ ), а затем отбросить строки и столбцы, удовлетворяющие соотношениям леммы 13.5. Затем мы можем выбрать одну из следующих альтернатив: воспользоваться леммой 13.5 для вычисления $$\mu_1(E_1)$$ (где $$E_1$$ - матрица, полученная из $$E$$ с помощью описанного выше процесса сокращения) или вычислить $$\mu_1(E_1)$$, воспользовавшись леммой 13.7, т. е. "раскладывая" $$E_1$$ по строкам и столбцам соответственно. Очевидно, что если число строк матрицы $$E_1$$ больше числа ее столбцов, то предпочтительнее "движение по столбцам" с помощью леммы 13.5, в противном случае для вычисления $$\mu_1(E_1)$$ целесообразно воспользоваться леммой 13.7.
13.8. ПРИМЕР. Найдем значение $$\mu_1(E)$$ для матрицы$$E=\left(\smallmatrix 0011\\ 0101\\0110\\1001\\1010\\1100 \endsmallmatrix\right).$$ Применяя лемму 13.5, получаем $$\mu_1(E) = \mu_1(E_1) - \mu_1(E_2)$$, где$$E_1 =\left(\smallmatrix 011\\ 101\\110\\001\\010\\100 \endsmallmatrix\right),$$ $$E_2=\left(\smallmatrix 011\\ 101\\110 \endsmallmatrix\right).$$ Легко видеть, что три первых строки матрицы $$E_1$$ являются "лишними", поэтому$$\mu_1(E_1) = \mu_1\left(\left(\smallmatrix 001\\ 010\\100 \endsmallmatrix\right)\right)=-1$$ (см. п.5 леммы 13.3). Применяя еще раз лемму 13.5, получаем (в силу утверждений леммы 13.3, что $$\mu_1(E_2) = \mu_1\left(\left(\smallmatrix 11\\ 01\\10 \endsmallmatrix\right)\right)-\mu_1((1,1))=1+1=2.$$ Следовательно, $$\mu_1(E) = \mu_1(E_1) - \mu_1(E_2) = -3$$.
Другой метод вычисления $$\mu_1(E)$$ основан на лемме 13.7:$$\begin{align*} \mu_1(E)= \mu_1\left(\left(\smallmatrix 0101\\ 0110\\1001\\1010\\1100 \endsmallmatrix\right)\right) - \mu_1\left(\left(\smallmatrix 01\\ 01\\ 10\\10\\11\endsmallmatrix\right)\right) \\ =\mu_1\left(\left(\smallmatrix 0110\\1001\\1010\\1100 \endsmallmatrix\right)\right)- \mu_1\left(\left(\smallmatrix 01\\10\\10 \endsmallmatrix\right)\right)- 1\\ =\mu_1\left(\left(\smallmatrix 1001\\1010\\1100 \endsmallmatrix\right)\right)- \mu_1\left(\left(\smallmatrix 11\\10\\10 \endsmallmatrix\right)\right) - 2\\ =\mu_1\left(\left(\smallmatrix 1010\\1100 \endsmallmatrix\right)\right)- \mu_1\left(\left(\smallmatrix 01\\ 10 \endsmallmatrix\right)\right) - 2=-3. \end{align*}$$
В качестве следствия леммы 13.7 получаем следующее утверждение, на котором основан алгоритм вычисления размерностного многочлена матрицы (см. ниже алгоритм A11 ).
13.9. ЛЕММА. Пусть $$E = (e_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$$ - $$n\!\times\! m$$ -матрица над $$\mathbb N$$ и $$\tau = (\tau_1,\dots,\tau_m) \in T = T(E)$$ (как и выше, $$T(E)$$ обозначает множество всех допустимых векторов матрицы $$E$$, т. е. множество всех элементов $$\tau \in \mathbb N^m$$, равных либо $$(0,\dots,0)$$, либо наименьшему общему кратному некоторых строк матрицы $$E$$ ). Пусть $$K$$ - матрица, состоящая из всех тех строк матрицы $$E$$, которые мажорируются вектором $$\tau$$ (для определенности предположим, что строки матрицы $$K$$ располагаются в том же порядке, в каком они расположены в матрице $$E$$ ). Кроме того, пусть $$\mbk = (k_1,\dots,k_m)$$ - одна из строк матрицы $$K$$ и $$K\setminus\mbk$$ - матрица, полученная удалением строки $$\mbk$$ из $$K$$. Тогда для любого подмножества $$J =\{ i_1,\dots,i_l\} $$ множества $$\mathbb N_m$$, такого, что $$i_1<\dots<i_l\ (1\leq l\leq m)$$, имеем$$\begin{equation} \mu_\tau (K,m) = \mu_\tau (K\setminus\mbk,m) - \mu_{\tau'} (K\setminus\mbk,J), \end{equation}$$ где $$\mu_\tau (K,m)$$, $$\mu_\tau(K\setminus\mbk,m)$$ суть соответственно коэффициенты $$\mu_\tau$$, определенные формулой (13.2) для матриц $$K$$ и $$K\setminus\mbk$$, а $$\mu_{\tau'}(K\setminus\mbk,J)$$ - аналогичные коэффициенты для вектора $$\tau'=(\tau_{i_1},\dots,\tau_{i_l})\in\mathbb N^l$$ (вместо $$\tau$$ ) и для $$(n-1)\!\times\!(m-l)$$ -матрицы, полученной из $$E$$ удалением столбцов с индексами $$j\in\mathbb N_m\setminus J$$.
ДОКАЗАТЕЛЬСТВО. Без потери общности можно предположить, что $$\mbk$$ - первая строка матрицы $$K$$. Из леммы 13.1 следует, что$$\mu_\tau(K,m) = \mu_1(H)$$ , где $$H= (h_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$$ - $$n\!\times\! m$$ -матрица с элементами $$h_{ij}=\begin{cases} 1, \text {если } e_{ij}= \tau_j,\\ 0, \text {если } e_{ij}\neq\tau_j,\end{cases}$$ $$(i = 1,\dots,n)$$. Аналогично, $$\mu_\tau(K\setminus\mbk,m) = \mu_1(H_1)$$ и $$\mu_{\tau'}(K\setminus\mbk,J) = \mu_1(H_2)$$, где матрица $$H_1$$ получена из $$H$$ отбрасыванием первой строки, а $$H_2$$ получена из $$H_1$$ отбрасыванием столбцов с индексами $$i_1,\dots,i_l$$. Применяя теперь лемму 13.7, получаем соотношение $$\mu_1(H) = \mu_1(H_1) - \mu_1(H_2)$$, из которого следует требуемое утверждение.
Вычисление коэффициентов $$\mu_\tau$$ $$(\tau \in T = T(E))$$ в (13.4) для размерностного многочлена произвольной $$n\!\times\! m$$ -матрицы $$E$$ (а, значит, и вычисление самого размерностного многочлена) может быть выполнено по следующей схеме: сначала применяем (13.6) к матрице $$E$$ (формируя матрицу $$K$$ тех строк матрицы $$E$$, которые мажорируются вектором $$\tau$$. Ясно, что коэффициенты $$\mu_\tau$$ для матриц $$K$$ и $$E$$ совпадают). Затем вычисляем значения $$\mu_\tau(K\setminus\mbk,m)$$ и $$\mu_{\tau'}(K\setminus\mbk,J)$$, снова применяя (13.6) и т. д., пока не получим "пустые" матрицы (т. е. матрицы с нулевым числом строк).
А11. АЛГОРИТМ $$(E, n,m, T, \mu)$$.
$$\begin{equation*}\\ \text{Дано: \qquad $m \in \mathbb N$,$n \in \mathbb N$;$E$-$n\!\times\! m$-матрица}\\ \text{Надо: \qquad $T$-множество допустимых векторов матрицы $E$;}\\ \text{ \qquad \qquad $\mu$- вектор типа $\mathbb Z$ с индексами из $T$.}\\ \text{Переменные: $J$ - множество типа $1..m$;}\\ \text{\qquad \qquad $K$- множество типа \{вектор типа $\mathbb N$ с индексами $1..m$\}.}\\ \text{Начало} \\ \text{сформировать множество $T$ допустимых векторов}\\ \text{цикл для каждого $\tau\in T$}\\ \text{\qquad \qquad $\mu_\tau:= 0$}\\ \text{\qquad \qquad $J:= \{ 1,\dots,m\}$}\\ \text{\qquad \qquad $K:= \{ \textbf{e}_i \mid \textbf{e}_i\leq \tau \} \text { где } \textbf{e}_i$ - строка матрицы $E$}\\ \text{ \qquad \qquad $v_\tau := 1$}\\ \text{\qquad \qquad NEXTINDEX $(J, K, v_\tau, \mu_\tau)$}\\ \text{конец цикла}\\ \text{Конец}\\ \text{Алгоритм NEXTINDEX $(J, K, v_\tau, \mu_\tau)$}\\ \text{Дано: $J$- множество типа $1..m$}\\ \text{\qquad $K$- множество типа \{вектор типа $\mathbb N$ с индексами $1..m$\}.}\\ \text{\qquad $v_\tau$ - элемент типа $\pm 1$}\\ \text{Надо:}\\ \text{$\mu_\tau$ - вектор типа $ \mathbb N$ с индексами из $T$.}\\ \text{Глобальные переменные: $m \in \mathbb N;$}\\ \text{\qquad $\tau$ - вектор типа $\mathbb N$ с индексами $1..m$.}\\ \text{Начало}\\ \text{цикл для каждой строки $\textbf{k}=\{k_1,\dots,k_m\}$ матрицы $K$, такой,}\\ \text{\qquad что $k_{i_1}=\tau_{i_1}$,}\\ \text{\qquad где $i_1$- первый элемент множества $J$}\\ \text{\qquad $K := K \setminus \textbf{k}$}\\ \text{\qquad $v_\tau := - v_\tau$}\\ \text{\qquad $J' := \{ j \in J \mid k_j=\tau_j\}$}\\ \text{\qquad $J=J\setminus J'$}\\ \text{\qquad выбор}\\ \text{\qquad \qquad $K=\emptyset \ J=\emptyset \implies \mu_\tau:= \mu_\tau+v_\tau$}\\ \text{\qquad \qquad $K\neq\emptyset \ J\neq\emptyset \implies \text{\tt NEXTINDEX}(J,K, v_\tau, \mu_\tau)$}\\ \text{\qquad конец выбора}\\ \text{\qquad $J := J \cup J'$}\\ \text{конец цикла}\\ \text{Конец} \end{equation*}$$Чтобы оценить асимптотическую сложность алгоритма A11 для достаточно больших $$n \in \mathbb N$$,
заметим, прежде всего, что при фиксированном векторе $$\tau =
(\tau_1,\dots,\tau_m) \in T$$ построение $$K=K(\tau )$$ требует не
более $$mn$$ сравнений чисел (на этом шаге мы запоминаем все
пары $$(k,j) \in \mathbb N_n \times \mathbb N_m$$, для которых $$e_{kj}=
\tau_j$$ ). Далее, выполнение элементарных операций
для всех вызовов алгоритма NEXTINDEX (для
фиксированного $$\tau$$ ) требует не более $$h_1h_2\dots
h_m$$ сравнений, где $$h_\nu=h_\nu(\tau)$$ $$(1\leq\nu\leq
m)$$ обозначает число
строк $$\textbf{k}=(k_1,\dots,k_m)$$ матрицы $$K(\tau)$$, таких,
что $$k_\nu=\tau_\nu$$ для всех $$\nu=1,\dots,m$$. Легко
видеть, что общее число операций для всех вызовов
алгоритма NEXTINDEX (с точностью до постоянного множителя это число
равно $$\sum\limits_{\tau\in T}h_1(\tau)\dots h_m(\tau )$$ ) не
превосходит $$$Card \{(a_1,\dots,a_m) \in \mathbb N^m \mid \text{ для каждого } \nu \in \mathbb N_m$$$ для каждого $$\nu \in
\mathbb N_m$$ существует $$i=i(\nu
)\in\mathbb N_n$$, такое, что $$a_\nu= e_{i\nu}\} $$, и это не
превосходит $$n^m$$.
Поэтому для достаточно больших $$n\in\mathbb N$$ асимптотическая сложность
алгоритма A11 имеет
порядок $$n^{m+1}$$.
Другой способ вычисления размерностного
многочлена $$\omega_E(t)$$ для $$n\!\times\!
m$$ -матрицы $$E$$ состоит в следующем. Для $$n<m$$ можно
вычислять
многочлен $$\omega_E(t)$$, пользуясь алгоритмом A9. Пусть $$n\geq m$$. В
этом случае применяем к $$E$$ соотношение (12.3), в
котором $$\textbf{e}$$ -
строка с максимальным значением элемента в первом столбце
матрицы $$E$$.
(Тривиальные случаи: если $$E=(0)$$, то $$\omega_E=0$$ ;
если $$n=1$$, применяем
алгоритм (12.3).) Легко видеть, что
число нулевых столбцов в матрице $$H$$ (см. (12.3)) больше, чем
в матрице $$E$$, и число строк в каждой из
матриц $$E\setminus\textbf{e}$$, $$K$$ меньше чем в $$E$$.
Затем применяем описанную процедуру к
матрице $$E\setminus\textbf{e}$$ и т.д., пока не получим матрицу,
размерностный
многочлен которой можно вычислить по алгоритму A9. В результате этого
процесса мы получаем представление требуемого
многочлена $$\omega_E(t)$$ в виде
линейной комбинации
многочленов $$\omega_{\textbf{e}},\omega_{H_1},\dots,\omega_{H_{n-1}}$$ (со
сдвинутыми аргументами),
таких, что каждая матрица $$H_i$$ имеет ровно $$i$$ строк и
число ее нулевых
столбцов на один больше, чем в $$E$$.
Многочлен $$\omega_{\textbf{e}}$$ и некоторые из
многочленов $$\omega_{H_i}$$ вычисляются по алгоритму A9 (в тех
случаях, когда этот алгоритм нужно применять в соответствии с вышеприведенными
рассуждениями). Для вычисления остальных
многочленов $$\omega_{H_i}$$ снова
применяем соотношение (12.3) и продолжаем в том же духе. Заметим, что
если первый столбец в матрице $$E$$ нулевой и $$m > 1$$, то
число операций в
вычислении $$\omega_E$$ по предлагаемой схеме совпадает с числом
операций при
вычислении размерностного многочлена $$n\!\times\! (m-1)$$ -матрицы.
Кроме того,
если $$E$$ - $$n\!\times\!1$$ -матрица, то все ее строки
кроме той, которая
содержит элемент $$\min_{1\leq i\leq n}\{ e_{i1}\}$$, являются
лишними, так что
вычисление размерностного многочлена по формуле $$\omega_E=\min_{1\leq
i\leq
n}\{ e_{i1}\}$$ требует $$(n-1)$$ операцию. Таким образом,
если $$f(n,m)$$ обозначает число элементарных операций (сложение,
сравнение или умножение)
необходимых для вычисления размерностного
многочлена $$\omega_E(t)$$ матрицы $$E$$ размера $$n\!\times\! m$$, то $$f(n,m)\leq(n-1)+f(n-1,m)+f(n-1,m-1)$$. Поскольку $$f(n,1)=n-1$$, имеем$$\begin{align*}
f(n,2)\leq 2(n-1) + f(n-1,2)\\
amp; \leq 2((n-1) + (n-2)) + f(n-2,2) \leq \dots\\
\leq 2((n-1) + (n-2) +\dots+1)= \frac {n(n-1)}2\cdot 2\leq
n^2;\\
f(n,3)\leq n^2+(n-1)^2+\dots+1 \leq n^3;\\
\vdots\\
f(n,k)\leq n^{k-1}+ (n-1)^{k-1}+\dots+1\leq n^k
\end{align*}$$
и т. д. Поэтому алгоритм вычисления размерностного многочлена, основанный на
приведенной схеме (см. алгоритм A12 ), имеет асимптотическую сложность $$O(n^m)$$.
А12. АЛГОРИТМ $$(E, n,m, \omega)$$.
$$\begin{equation}\\ \text{Дано: \quad $n\in\mathbb N; m\in\mathbb N$;$n\!\times\!m$-матрица$E$.} \\ \text{Надо: \qquad$\omega(t)=\omega_E(t)$- многочлен Гильберта матрицы $E$.}\\ \text{Пер.: \qquad $h \in \mathbb N$}\\ \text{\qquad $J$- множество элементов типа $1..m$;}\\ \text{\qquad $\textbf{e}$- вектор типа $\mathbb N$ с индексами $1..m$;}\\ \text{\qquad $F$- матрица типа $\mathbb N$, число столбцов которой не более $m$,}\\ \text{ \qquad а число строк - не более $n$.}\\ \text{Начало}\\ \text{$h:=n$}\\ \text{$F:= E$}\\ \text{если $h \leq m $ то }\\ \text{\qquad Алгоритм A9 $(E,n,m,\omega)$}\\ \text{иначе}\\ \text{\qquad $J:=\{$ ненулевые столбцы $F\}$}\\ \text{\qquad если $J=\emptyset $ то $\omega(t) := 0$}\\ \text{\qquad иначе если $Card J = 1$ то}\\ \text{\qquad\qquad $c:=$ минимальный элемент столбца $j \in J$}\\ \text{\qquad\qquad $\omega := \binom {t+m}m-\binom {t+m-c}m$}\\ \text{\qquad иначе}\\ \text{\qquad\qquad $j:=\{$ первый элемент множества $J\}$}\\ \text{\qquad \qquad $\textbf{e}:=\{$ первая строка матрицы $F$ с минимальным}\\ \text{\qquad\qquad\quad элементом в $j$ -м столбце $\}$}\\ \text{\qquad\qquad $F:= F\setminus\textbf{e}$}\\ \text{\qquad\qquad Алгоритм A12$(F,h-1,m,\omega)$}\\ \text{\qquad\qquad $v(t):= \omega(t)$}\\ \text{\qquad\qquad $F:= \{\textbf{f}-\textbf{e} \mid \textbf{f}$ - строка матрицы $F, \textbf{f} \neq \textbf{e}\} $}\\ \text{\qquad\qquad Алгоритм A12 $(F,h-1,m,\omega)$}\\ \text{\qquad\qquad $\omega(t) := v(t) - \omega (t-|\textbf{e}|)$}\\ \text{\qquad конец если} \\ \text{конец если}\\ \text{Конец} \end{equation}$$Символ $$\dotminus$$, которым мы пользуемся в алгоритме A12, обозначает следующую операцию на векторах:$$(a_1,\dots,a_m) \dotminus(b_1,\dots,b_m) = (c_1,\dots,c_m),$$ где $$c_i=\max(a_i-b_i,0)$$ для всех $$i=1,\dots,m$$. При этом, если $$m > 2$$, то $$e_i$$ $$(1\leq i\leq m)$$ обозначает $$i$$ -ю координату элемента $$\textbf{e} \in \mathbb N^m$$.
В заключение этого параграфа рассмотрим алгоритм вычисления размерностного
многочлена, асимптотическая сложность которого
меньше асимптотической сложности алгоритмов A9, A10, A11 и A12. Кроме того,
представим алгоритм вычисления
Пусть $$\mathbb Q[t]$$ - кольцо многочленов над полем рациональных чисел. Для каждого $$s\in\mathbb N$$ пусть $$\Delta_s$$ и $$\Delta^{-1}$$ обозначают операторы, действующие на $$\mathbb Q[t]$$ следующим образом:$$\begin{equation}\ \Delta_s(f(t))=f(t)-f(t-s) \end{equation}$$ и если $$f(t) =\sum_{i\in\mathbb N} a_i\binom{t+i}i$$ $$(a_i\in\mathbb Q)$$ для всех $$i\in\mathbb N$$, то$$\begin{equation}\label{13.7apos;} \Delta^{-1}f(t)=\sum_{i\in\mathbb N} a_i\binom {t+1+i}{i+1}. \qquad \qquad \qquad \ecno(13.7') \end{equation}$$
Отметим, что операторы $$\Delta_s$$ и $$\Delta^{-1}$$ $$(s \in \mathbb N)$$, удовлетворяют следующему тождеству:$$\begin{equation} \Delta_s\Delta^{-1}f(t) =f(t)+f(t-1)+ \dots+f(t-s+1). \end{equation}$$ В частности,$$\Delta_1\Delta^{-1}= \id_{\mathbb Q[t]}.$$ Действительно, пусть$$f(t) =\sum\limits_{i\in\mathbb N} a_i\binom {t+i}i$$ $$a_i\in\mathbb Q$$ для всех $$i\in\mathbb N$$, и $$a_i=0$$ для почти всех $$i\in\mathbb N$$ и пусть $$s \in \mathbb N$$. По (11.4) имеем$$\begin{multiline*} \Delta_s\Delta^{-1}f(t) =\sum\limits_{i\in\mathbb N} a_i\left[\binom{t+i+1}{i+1}-\binom {t+i+1-s}{i+1}\right] =\sum\limits_{i\in\mathbb N} a_i\sum\limits_{r=0}^{s-1} \binom {t+i+1-s+r}i =\sum\limits_{i\in\mathbb N} a_i\sum\limits_{r=0}^{s-1} \binom {t+i-r}i\\ =\sum\limits_{r=0}^{s-1} \sum\limits_{i\in\mathbb N} a_i\binom {t+i-r}i =\sum\limits_{r=0}^{s-1} f(t-r). \end{multliine*}$$
13.10. ЛЕММА. Пусть $$E=(e_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$$ - $$n\!\times\!m$$ - матрица над $$\mathbb N$$, $$k\in\mathbb N_m$$ и $$a=\min_{i=1}^n\{e_{ik} \mid e_{ik}\neq 0\}$$. Через $$E_1$$ обозначим матрицу, полученную из $$E$$ удалением $$k$$ -го столбца и всех строк с ненулевым элементом в $$k$$ -м столбце. Далее, пусть $$H =(h_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$$ - $$n\!\times\! m$$ -матрица с элементами$$\[ h_{ij}=\begin{cases} \max(e_{ik}- a,0), \text { если }j=k\\ e_{ij}, \text { если } j\neq k\end{cases}\quad (1\leq i\leq n,\ 1\leq j\leq m).$$ Тогда$$\begin{equation} \omega_E(t)=\Delta_a\Delta^{-1}\omega_{E_1}(t)+\omega_H(t-a), \end{equation}$$ где $$\omega_E(t)$$, $$\omega_H(t)$$ и $$\omega_{E_1}(t)$$ - размерностные многочлены матриц $$E$$, $$H$$ и $$E_1$$ соответственно.
В частности, если$$E= \begin{pmatrix} k 0\dots0\\ \begin{matrix} 0\\ \vdots \\ 0\end{matrix} E_1\end{pmatrix},$$ где $$e_{11}=k$$, а все остальные элементы первого столбца и первой строки равны нулю, то $$\omega_E(t)=\Delta_k\cdot\Delta^{-1}\omega_{E_1}(t)$$.
ДОКАЗАТЕЛЬСТВО. Применяя формулу (12.2) к матрице $$E$$ и вектору $$(0,\dots,0,a,0,\dots,0)$$ ( $$a$$ - $$k$$ -я координата этого вектора), получаем$$\omega_E(t) = \omega_{E\cup (0,\dots,0,a,0,\dots,0)}(t) + \omega_H(t-a).$$ Теперь применим (12.2) к матрице $$E\cup (0,\dots,0,a,0,\dots,0)$$ и вектору $$(0,\dots,0,1,0,\dots,0)$$ (где 1 стоит на $$k$$ -м месте). По теореме 12.8(8) получим$$\omega_{E\cup (0,\dots,0,a,0,\dots,0)}(t)= \omega_{E_1}(t)+ \omega_{E\cup (0,\dots,0,a-1,0,\dots,0)}(t-1).$$ Повторяя эту операцию $$a$$ раз, получим равенство$$\omega_{E\cup (0,\dots,0,a,0,\dots,0)}(t) =\omega_{E_1} (t) + \omega_{E_1}(t-1)+\dots+ \omega_{E_1}(t-(a-1)),$$ откуда следует (13.9) (см. (13.8)).
Теперь можно предложить следующую схему вычисления размерностного многочлена $$\omega_E(t)$$ матрицы $$E=(e_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$$, основанную на формуле (13.9). Сначала, выбрав вектор $$(a,0,\dots,0) \in \mathbb N^m$$, где $$a=\min_{1\leq i\leq n} \{ e_{i1}\ \mid e_{i1}\neq 0\}$$, и применив лемму 13.10, сведем нашу задачу к вычислению размерностного многочлена матрицы $$E_1$$ с $$(m-1)$$ столбцом и размерностного многочлена матрицы $$H = (h_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$$, такой, что $$0\leq h_{i1}< e_{i1}$$ $$(1\leq i\leq n)$$. Для определения $$\omega_H(t)$$ применим формулу (13.9) (с матрицей $$H$$ вместо $$E$$ ) и продолжим процесс до тех пор, пока не получим представление $$\omega_E(t)$$ в виде суммы размерностных многочленов матриц с $$(m-1)$$ столбцом и размерностного многочлена $$\omega_{H_1}(t)$$, где $$H_1$$ - $$n\!\times\! m$$ -матрица с нулевым первым столбцом. Для вычисления $$\omega_{H_1}(t)$$ применяем описанную процедуру ко второму столбцу и т. д.
13.11. ПРИМЕР. Вычислим многочлен Гильберта $$\omega_E(t)$$ матрицы$$E=\begin{pmatrix} 200\\020\end{pmatrix}.$$
Сначала находим $$a=2$$. Применяя (13.9), получаем$$\omega_E(t)=\Delta_2\Delta^{-1}\omega_{E_1}(t)+\omega_H(t-2),$$ где $$E_1 =(2,0)$$ и $$H=\begin{pmatrix} 000\\020\end{pmatrix}$$. Ясно, что $$\omega_H(t)=0$$ (см. теорему 12.8(6)) и $$\omega_{E_1}(t)=\binom {t+2}2 - \binom {t+2-2}2$$, следовательно, (см. 13.8)$$\begin{align*} \omega_E(t){} = \Delta_2\Delta^{-1}\omega_{E_1}(t) = \omega_{E_1}(t) + \omega_{E_1}(t-1) \\ {}= \binom {t+2}2 - \binom t2 + \binom {t+1}2-\binom {t-1}2 = 4t. \end{align*}$$
Заметим, что вычисление многочлена Гильберта $$\omega_E(t)$$ по одному из алгоритмов A9, A10, A11 или A12 приводит к представлению этого многочлена в виде $$\omega_E(t) = \binom {t+3}3-2\binom {t+3-2}3 + \binom {t+3-4}3$$. Однако, применяя лемму 13.10, мы получаем многочлен $$\omega_E(t)$$ в виде суммы многочленов вида $$a_k\binom {t+i}k$$ $$(i \in\mathbb Z$$, $$k \in \mathbb N$$, $$a_k\in\mathbb Z)$$. Максимальная степень этих многочленов меньше степени многочленов, фигурирующих в подобном представлении для $$\omega_E(t)$$, когда $$\omega_E(t)$$ вычисляется по одному из алгоритмов A9, A10, A11 или A12.
Следующая лемма дает возможность оценивать степень многочлена Гильберта и
вычислять его
13.12. ЛЕММА. Пусть $$E = (e_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$$ - $$n\!\times\! m$$ -матрица над $$\mathbb N$$ и $$\tau\le m$$ - неотрицательное целое число. Тогда $$\deg\omega_E(t)<\tau$$ если и только если для любого подмножества $$I$$, состоящего из $$m-\tau$$ элементов множества $$\{1,\dots,m\}$$, существует строка $$e_I$$ матрицы $$E$$ , такая, что все элементы этой строки, стоящие в столбцах с индексами из $$I$$ , равны нулю. В частности, $$\omega_E(t)=\const$$ тогда и только тогда, когда $$E$$ содержит диагональную подматрицу.
Доказательство леммы проводится индукцией по сумме элементов матрицы $$E$$ и оставляется читателю в качестве упражнения.
Матрицу $$E$$ над $$\mathbb N$$ назовем нормализованной, если каждый столбец матрицы $$E$$ содержит нуль. Ниже будет показано, что если $$E$$ - нормализованная $$n\!\times\!m$$ -матрица, то алгоритм вычисления размерностного многочлена $$\omega_E(t)$$, основанный на лемме 13.10, требует меньшего числа операций, чем для произвольной $$n\!\times\! m$$ -матрицы. В то же время, для сведения задачи вычисления размерностного многочлена произвольной $$n\!\times\! m$$ -матрицы над $$\mathbb N$$ к аналогичной задаче для нормализованной $$n\!\times\! m$$ -матрицы можно воспользоваться теоремой 12.8(9).
13.13. ЛЕММА. Пусть $$E = (e_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$$ - $$n\!\times\! m$$ -матрица над $$\mathbb N$$ и предположим, что $$\deg \omega_E=0$$.
ДОКАЗАТЕЛЬСТВО. (1) Если $$e_{11}=0$$, то в $$E$$ имеется нулевая строка, следовательно, $$\omega_E=0$$ (см. теорему 12.8(6)). Если $$e_{11}>0$$, то применяя (12.2) к $$E$$ и $$\textbf{e}=(1,0,\dots,0)\in\mathbb N^m$$, получаем$$\omega_E = \omega_{E\cup\textbf{e}}+\omega_H = \omega_{E_1}+ \omega_H, \text{ где } H =\begin{pmatrix} e_{11}-1 0\dots0\\ \begin{matrix} 0\ \vdots \\ 0\end{matrix} E_1\end{pmatrix}.$$ Таким образом, индукция по $$e_{11}$$ дает требуемый результат.
(2) Лемма 13.12 утверждает, что $$E$$ содержит строку, в которой ненулевой может быть только первая координата. Значит $$H$$ содержит нулевую строку, следовательно, $$\omega_H=0$$.
(3) Соотношение (13.10) следует из (12.2), записанного для $$E$$ и $$(a,0,\dots,0)\in\mathbb N^m$$.
Пользуясь леммой 13.13, можно предложить следующий метод вычисления многочлена Гильберта $$\omega_E$$ матрицы $$E$$ в случае, когда $$\deg\omega_E=0$$: применить соотношение (13.10) к $$\omega_E$$ (где $$a$$ - минимальный ненулевой элемент в первом столбце матрицы $$E$$ ), затем выписать аналогичное представление для $$E_2$$ и т. д. После конечного числа таких шагов получим представление многочлена $$\omega_E$$ в виде суммы многочленов Гильберта матриц $$F_1,\dots,F_r$$ $$(r\in\mathbb N$$, $$r\geq 1)$$ с $$(m-1)$$ столбцами и многочлена Гильберта $$\omega_H$$, где элементы матрицы $$H=(h_{ij})_{\substack{1\leq i\leq n\\1\leq j\leq m}}$$ равны$$h_{ij}=\begin{cases} e_{ij}, \text{если } 1\leq i\leq n,\ 2\leq j\leq m\\ 0, \text{если } 1\leq i\leq n,\ j=1,\end{cases}$$ так что $$\omega_H=0$$ (см. лемму 13.13(2)). Применяя описанную процедуру к каждой из матриц $$F_1,\dots,F_r$$, мы сводим вычисление многочлена $$\omega_E$$ к вычислению многочленов Гильберта для некоторых матриц с $$(m-2)$$ столбцами и т.д., пока не получим матрицы, состоящие из единственного столбца. Как мы знаем, многочлен Гильберта такой матрицы совпадает с ее минимальным элементом.
В общем случае (без условия $$\deg \omega_E=0$$ ) вычисление размерностного многочлена $$\omega_E(t)$$ для $$n\!\times\! m$$ -матрицы $$E=(e_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$$ по описанной схеме (используя (13.9) вместо (13.10)) можно свести к вычислению размерностных многочленов матриц, число столбцов в которых меньше $$m$$, и размерностных многочленов некоторых $$n\!\times\! m$$ -матриц с нулевым первым столбцом. Более точно: если первый столбец матрицы $$E$$ содержит ненулевые элементы, то мы полагаем $$a=\min_{1\leq i\leq n} \{ e_{i1} | e_{i1}\neq0 \} $$ и применяем (13.19). Затем применяем то же самое соотношение к $$H$$ (см. лемму 13.10) и т. д. В результате получим разложение многочлена $$\omega_E(t)$$ в сумму многочленов вида $$\omega_{E_i}(t-a_i)$$, где $$a_i\in \mathbb N$$ и $$E_i$$ - либо матрица, число столбцов в которой меньше $$m$$, либо $$n\!\times\! m$$ -матрица с нулевым первым столбцом. Для вычисления размерностных многочленов матриц второго типа применяем описанный метод ко второму столбцу и т. д., пока не получим представление многочлена $$\omega_E(t)$$ в виде суммы размерностных многочленов матриц, число столбцов в которых меньше $$m$$, и размерностных многочленов матриц с не более чем двумя ненулевыми столбцами. Размерностный многочлен матрицы последнего типа может быть найден с помощью следующего утверждения.
13.14. ЛЕММА. Пусть$$E=\begin{pmatrix} e_{11} e_{12} 0 \hdots 0 \\ e_{21} e_{22} 0 \hdots 0 \\ \vdots \vdots \vdots \ddots \vdots \\ e_{n1} e_{n2} 0 \hdots 0 \end{pmatrix}$$ - нормализованная $$n\!\times\! m$$ -матрица над $$\mathbb N\ (m\geq 2)$$ . Предположим, что $$0 = e_{11}< e_{21}<\dots< e_{n1}$$ и $$e_{12}> e_{22}>\dots> e_{n2}= 0$$. Тогда$$\begin{equation} \omega_E(t)=\sum_{i=1}^{n-1}\Delta_{(e_{i+1,1}-e_{i1})} \Delta^{-1}\omega_{\textbf{e}_i}(t-e_{i1}), \end{equation}$$ где $$\textbf{e}_i= (e_{i2},0,\dots,0) \in \mathbb N^{m-1}\ (i=1,\dots,n-1)$$.
ДОКАЗАТЕЛЬСТВО. Воспользуемся индукцией по $$n$$. Случай $$n=1$$ тривиален. Пусть $$n>1$$, и предположим, что утверждение леммы доказано для всех матриц, число строк которых меньше $$n$$. Для доказательства соотношения (13.11) для $$n\!\times\! m$$ -матрицы $$E = (e_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$$, у которой $$e_{ij}=0$$ $$(1\leq i\leq n$$, $$3\leq j\leq m)$$, прежде всего заметим, что если $$a=\min_{1\leq i\leq n} \left( e_{i1} \mid e_{i1}\neq0\right) =e_{21}$$, то$$\omega_E(t) = \Delta_a\Delta^{-1} \omega_{E_1}(t)+\omega_H(t-a),$$ где $$E_1 = (e_{12},0,\dots,0) \in \mathbb N^{m-1}$$ и$$H=\begin{pmatrix} 0 e_{12} 0 \hdots 0 \\ 0 e_{22} 0 \hdots 0 \\ e_{31}-e_{21} e_{32} 0 \hdots 0 \\ \vdots \vdots \vdots \ddots \vdots \\ e_{n1}-e_{21} e_{n2} 0 \hdots 0 \end{pmatrix}$$ (см. лемму 13.10). Первая строка матрицы $$H$$ является лишней, следовательно, $$\omega_H=\omega_{H_1$$, где$$H_1=\begin{pmatrix} 0 e_{22} 0 \hdots 0 \\ e_{31}-e_{21} e_{32} 0 \hdots 0 \\ \vdots \vdots \vdots \ddots \vdots \\ e_{n1}-e_{21} e_{n2} 0 \hdots 0 \end{pmatrix}.$$ По предположению индукции имеем$$\omega_H(t) = \omega_{H_1}=\sum_{i=2}^{n-1} \Delta_{(e_{i+1,1}-e_{i1})} \Delta^{-1} \omega_{ \textbf{e}_i}(t-e_{i1}),$$ следовательно,$$\begin{align*} \omega_E(t) = \Delta_{e_{21}} \Delta^{-1}\omega_{E_1}(t) +\sum_{i=2}^{n-1}\Delta_{(e_{i+1,1}-e_{i1})}\Delta^{-1}\omega_{\textbf{e}_i}(t-e_{i1})\ =\smash{\sum_{i=1}^{n-1}}\Delta_{(e_{i+1,1}-e_{i1})}\Delta^{-1}\omega_{\textbf{e}_i}(t-e_{i1}). \tag*\qedsymbol \end{align*}$$
13.15. СЛЕДСТВИЕ. Пусть$$E=\begin{pmatrix} e_{11} e_{12} \\ e_{21} e_{22} \\ \vdots \vdots \\ e_{n1} e_{n2} \end{pmatrix}$$ - $$n\!\times\! 2$$ -матрица над $$\mathbb N$$, такая, что $$0 = e_{11}< e_{21}< \dots < e_{n1}$$, $$e_{12}> e_{22}>\dots> e_{n2}= 0$$. Тогда $$\begin{equation} \omega_E(t)=\sum_{i=1}^{n-1}(e_{i+1,1}-e_{i1}) e_{i2}. \ \end{equation}$$
А13. АЛГОРИТМ $$(E, n,m, \omega)$$.
$$\begin{equation}\\ \text{Дано: \quad $n\in\mathbb N;\ m\in\mathbb N$; $n\!\times\!m$-матрица $E$. }\\ \text{Надо:\qquad $\omega_E(t)$- многочлен Гильберта матрицы $E$.}\\ \text{Переменные: $P_0, P_1$- многочлены;}\\ \text{\qquad $N_S$- текущее значение первой координаты;}\\ \text{\qquad $N_R$- следующее значение первой координаты;}\\ \text{\qquad $E_0$- последовательность $(m-1)$-мерных векторов.}\\ \text{Начало}\\ \text{$\omega(t):=0$}\\ \text{если $n=0$ тоесли $n=0$ то $\omega(t):=\binom {t+m}m$}\\ \text{иначе $\textbf{v}:=(v_1,\dots,v_m)$, \ где $v_j =\min_{1\leq i\leq n} \{e_{ij}\}\ (j=1,\dots,m)$}\\ \text{ \qquad $E := (e_{ij}-v_j)_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$}\\ \text{\qquad $K :=$ \{индексы ненулевых столбцов матрицы $E$\}}\\ \text{\qquad выбор}\\ \text{\qquad $Card K=2$, $K=\{ j,p\} \implies$ сортировать строки по возрастанию $j$-го столбца}\\ \text{\qquad \qquad удалить лишние строки }\\ \text{$\omega:=\omega(t)+\sum\limits_{i=1}^{n-1}\Delta_{(e_{i+1,j}-e_{ij})}\Delta^{-1}\omega_{\textbf{e}_i}(t-e_{ij})$,}\\ \text{\qquad \qquad \qquad где $\textbf{e}_i=(e_{ip},0,\dots,0)\in\mathbb N^{m-1}$}\\ \text{\qquad $Card K>2 \Rightarrow$ взять $k \in K$}\\ \text{\qquad \qquad переставить $k$-й столбец с первым}\\ \text{\qquad \qquad $N_S := 0$}\\ \text{\qquad \qquad $E_0 := \emptyset$}\\ \text{\qquad \qquad цикл для каждого ненулевого $e_{i1}$ в возрастающем порядке}\\ \text{\qquad \qquad \qquad $N_R := e_{i1}$}\\ \text{\qquad \qquad \qquad $E_0$: добавить последовательность строк}\\ \text{\qquad \qquad \qquad \qquad $\{ (e_{j2},\dots,e_{jm})|e_{j1}= N_S\}$}\\ \text{\qquad \qquad \qquad $N_0 :=$ число векторов в $E_0$}\\ \text{\qquad \qquad \qquad Алгоритм A13 $(E_0,N_0,m-1,P_0(t))$}\\ \text{\qquad \qquad \qquad $P_0(t):=\Delta_{(N_R-N_S)}\Delta^{-1}P_0(t)$}\\ \text{\qquad \qquad \qquad $\omega(t):=\omega(t)+P_0(t-N_S)$}\\ \text{\qquad \qquad \qquad $N_S:=N_R$}\\ \text{\qquad \qquad конец цикла}\\ \text{\qquad \qquad $E$: обнулить первый столбец}\\ \text{\qquad \qquad Алгоритм A13 $(E,n,m,P_1(t))$}\\ \text{\qquad \qquad $\omega(t):=\omega(t)+P_1(t-N_S)$}\\ \text{\qquad конец выбора}\\ \text{\qquad $\omega(t):=\omega(t-|\textbf{v}|)+\binom{t+m}m-\binom{t+m-|\textbf{v}|}m$}\\ \text{конец если}\\ Конец \end{equation}$$Приведенный здесь алгоритм A13 вычисления многочлена Гильберта $$\omega_E(t)$$ для $$n\!\times\!m$$ -матрицы $$E$$ основан на данной выше схеме. В соответствии с ней, воспользуемся (13.8), чтобы представить многочлен $$\omega_E(t)$$ в виде суммы многочленов Гильберта матриц, которые содержат менее $$m$$ столбцов, и многочлена Гильберта $$n\!\times\!m$$ -матрицы $$E'$$, содержащей не более двух ненулевых столбцов (без потери общности можно считать, что ненулевыми являются два первых столбца матрицы $$E'$$ ). Многочлен $$\omega_{E'}(t)$$ вычисляется с помощью соотношения (13.10). Сначала переупорядочим строки так, чтобы элементы первого столбца удовлетворяли условию леммы 13.14 (такое переупорядочение требует $$\sim n\log n$$ элементарных операций). Тогда видно, что если второй ненулевой столбец не упорядочен в обратном порядке, то матрица $$E'$$ содержит лишние строки (в точности те строки $$\textbf{e}_i \ (1\leq i\leq n)$$, в которых $$e_{12}\geq e_{j2}$$ для некоторого $$j \in \mathbb N,\ 1\leq j<i$$ ). Таким образом, получаем следующую оценку числа $$f(n,m)$$ элементарных операций, которые требуются для вычисления многочлена Гильберта $$\omega_E(t)$$ для $$n\!\times\! m$$ -матрицы $$E$$ с помощью алгоритма A13:$$\begin{align*} f(n,m)\leq n\log n+f(n,m-1)+\sum_{i=1}^kf(b_i,m-1)\\ \leq n\log n+nf(n,m-1) \end{align*}$$ где $$1\leq k<n;\ b_1,\dots,b_k \in \N$$ ; $$1\leq b_i\leq n$$ $$(i=1,\dots,k)$$. Следовательно, алгоритм A13 имеет асимптотическую сложность $$\sim n^{m-1 \log n$$ при $$m\geq 2$$ (если $$m=1$$, то асимптотическая сложность $$\sim n$$ ).
13.16. ПРИМЕР. Вычислим многочлен Гильберта матрицы$$E=\left( \smallmatrix 1 0 0 1 \\ r-2 0 1 0 \\ r-3 0 2 0 \\[-6pt] \vdots \vdots \vdots \vdots \\ i 0 r-i-1 0 \\[-6pt] \vdots \vdots \vdots \vdots \\ 1 0 r-2 0 \\ 0 1 0 r-2\endsmallmatrix\right)$$ $$(r\in \mathbb N,\ r\geq 3)$$ при помощи алгоритма A13. В процессе вычислений последовательно применяем (13.8), начиная с последнего столбца матрицы $$E$$. Прежде всего запишем$$\omega_E(t) = \Delta_1\Delta^{-1}\omega_{E_1}(t) + \omega_H(t-1) = \omega_{E_1}(t) + \omega_H(t-1),$$ где$$E_1=\left( \smallmatrix r-2 0 1 \\ r-3 0 2 \\[-6pt] \vdots \vdots \vdots \\ 1 0 r-2\endsmallmatrix\right),H=\left( \smallmatrix 1 0 0 0 \\ r-2 0 1 0 \\ r-3 0 2 0 \\[-6pt] \vdots \vdots \vdots \vdots \\ i 0 r-i-1 0 \\ \vdots \vdots \vdots \vdots \\ 1 0 r-2 0 \\ 0 1 0 r-3\endsmallmatrix\right).$$ По теореме 12.8(8) имеем$$\begin{align*} \omega_H(t-1)= \omega_{(1,0,r-3)}(t-1) =\binom{t-1+3}3-\binom{t-1+3-(r-2)}3\\ = \binom {t+2}3 - \binom {t+4-r}3. \end{align*}$$ Применяя (12.2) к $$E_1$$ и $$(1,0,1)$$, получаем $$\omega_{E_1}(t)=\omega_{(1,0,1)}(t)+ \omega_{H_1}(t-2)$$, где$$H_1=\left( \smallmatrix r-3 0 0 \\ r-4 0 1 \\[-6pt] \vdots \vdots \vdots \\ 1 0 r-4 \\ 0 0 r-3\endsmallmatrix\right),$$ так что из формулы (13.10) следует, что$$\begin{align*} \omega_{H_1}(t-2) = \sum_{i=1}^{r-3}\Delta_1\Delta^{-1}\omega_{(r-2-i,0)}(t-2-(i-1))\\ =\sum_{i=1}^{r-3}\omega_{(r-2-i,0)}(t-i-1)\\ =\sum_{i=1}^{r-3}\left[\binom {t-i-1+2}2 -\binom {t-i-1+2-(r-2-i)}2\right]\\ =\sum_{i=1}^{r-3}\left[\binom {t-i+1}2 -\binom {t+3-r}2\right]\\ = \frac{(r-3)(r-2)}2 t - \frac{(r-2)(r-3)(2r-5)}6. \end{align*}$$ Поэтому,$$\begin{align*} \omega_{E_1}(t)={}\binom{t+3}3-\binom{t+3-2}3+\frac{(r-3)(r-2)}2t -\frac{(r-2)(r-3)(2r-5)}6 \\ ={}(t+1)^2 + \frac{(r-3)(r-2)}2 t -\frac{(r-2)(r-3)(2r-5)}6, \end{align*}}$$ следовательно,$$\begin{align*} \omega_E(t)={}\binom {t+2}3 - \binom {t+4-r}3 + (t+1)^2\\ +\frac{(r-3)(r-2)}2 t-\frac{(r-2)(r-3)(2r-5)}6 \\ ={}\frac r2t^2+\frac{r+2}2t-\frac{r^3-6r^2+11r-12}6. \end{align*}$$
Рассмотрим задачу вычисления
$$E = (e_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$$ — $$n\!\times\! m$$ -матрица над $$\mathbb N$$ и$$\begin{equation} \omega_E(t) =\sum_{i=0}^m a_i(E)\binom {t+i}i \end{equation}$$ ее многочлен Гильберта. Тогда по теореме 12.8(7) имеем$$a_m(E)=\begin{cases} 1,\text {если матрица $E$ пустая } (n=0)\\ 0,\text {в противном случае.}\end{cases}$$ Из теоремы 12.8(9) и леммы13.12 что$$a_{m-1}(E)=\begin{cases} 0,\text {если матрица $E$ пустая,}\\ \sum_{j=1}^m\min_{1\leq i\leq n} \{ e_{ij}\} ,\text {в противном случае.}\end{cases}$$ Вычисление коэффициента $$a_{m-2}(E)$$ (при $$m\geq 2$$ ) может основываться на следующем утверждении.
13.17. ЛЕММА. Пусть $$E = (e_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$$ — $$n\!\times\! m$$ -матрица над $$\mathbb N$$, такая, что $$m>1$$ и первый столбец матрицы $$E$$ нулевой. Пусть $$\omega_E(t) =\sum\limits_{i=0}^\tau a_i(E) \binom {t+i}i$$ — многочлен Гильберта матрицы $$E$$ и $$0<\deg\omega_E\leq \tau\ (\tau\in\mathbb N_m)$$. Далее, пусть $$E_1$$ — $$n\!\times\!(m-1)$$ -матрица, полученная из $$E$$ удалением первого (нулевого) столбца. Тогда $$\deg \omega_{E_1}\leq \tau-1$$ и $$a_\tau(E)=a_{\tau-1}(E_1)$$.
ДОКАЗАТЕЛЬСТВО. Применяя (12.2) к $$E$$ и $$(1,0,\dots,0) \in \mathbb N^m$$, получим, что $$\omega_E(t)=\omega_{E_1}(t)+\omega_E(t-1)$$. Значит, если$$$\omega_E(t) =\sum_{i=0}^\tau a_i(E) \binom {t+i}i,$ то \begin{align*} \omega_{E_1}(t)=\sum_{i=0}^\tau a_i(E_1) \binom {t+i}i =\sum_{i=0}^\tau a_i(E) \left[ \binom {t+i}i- \binom {t+i-1}i\right]\\ = \sum_{i=0}^{\tau-1} a_{i+1}(E) \binom {t+i}i, \end{align*}$$ следовательно, $$\deg \omega_{E_1}\leq\tau-1$$ и $$a_i(E_1) = a_{i+1}(E)$$ для всех $$i=0$$, $$1,\dots,\tau-1$$. В частности, $$a_\tau(E)=a_{\tau-1}(E_1)$$.
Отметим, что если для $$n\!\times\! m$$ -матрицы $$E = (e_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$$ степень многочлена Гильберта $$\omega_E(t)= \smash{\sum\limits_{i=0}^m} a_i(E) \binom {t+i}i$$ меньше или равна $$\tau$$ $$(\tau\in\mathbb N$$, $$0\leq \tau\leq m)$$, то$$\begin{equation} a_\tau(E) = a_\tau(E_1) + a_\tau(E_2), \end{equation}$$ где $$a=\min_{1\leq i\leq n}\{ e_{i1}| e_{i1}\neq0\}$$, матрица $$E_1$$ получена из $$E$$ удалением первого столбца и всех строк с нулем в первом столбце, а $$E_2= (e'_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$$ — $$n\!\times\! m$$ -матрица с элементами$$e'_{ij}=\begin{cases} e_{ij}, \text{если } j\neq 1 \\ \max\{ e_{i1}-a, 0\} ,\text{если } j=1\end{cases} \ (1\leq i\leq n,\ 1\leq j\leq m).$$ (Соотношение (13.14) легко может быть установлено применением (12.2) к $$E$$ и $$(a,0,\dots,0)\in\mathbb N^m$$.)
Прежде чем вычислять коэффициент $$a_{m-2}(E)$$ многочлена Гильберта (13.13), заметим, что, без потери общности, можно предполагать, что $$\deg\omega_E\leq m-2$$. Действительно, применяя (12.2) к $$E$$ и $$\textbf{e}=\bigl(\min\limits_{1\leq i\leq n}\{ e_{i1}\} ,\dots,\min\limits_{1\leq i\leq n}\{e_{im}\}\bigr)$$,получаем, что$$\omega_E(t) =\binom {t+m}m - \binom {t+m- |\textbf{e}|}m + \omega_{E'}(t-|\textbf{e}|),$$ где $$E' = (e'_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$$ — матрица с элементами $$e'_{ij}=e_{ij}- \min_{1\leq i\leq n}\{ e_{ij}\} $$ $$(1\leq i\leq n,\ 1\leq j\leq m)$$. Пользуясь (11.4), можно переписать последнее представление $$\omega_E(t)$$ в виде$$\begin{align*} \omega_E(t) ={}\sum_{i=0}^{|\textbf{e}|-1} \binom {t+m-1-i}{m-1} + \omega_{E'}(t-|\textbf{e}|) \\ ={} \smu{2} |\textbf{e}|\binom {t+m-1}{m-1}\!-\!\sum_{i=1}^{|\textbf{e}|-1} \left[\!\binom {t+m-1}{m-1}\!-\!\binom {t+m-1-i}{m- 1}\!\right] +\omega_{E'}(t-|\textbf{e}|) \\ ={} |\textbf{e}|\binom {t+m-1}{m-1} - \sum_{i=1}^{|\textbf{e}|-1} \sum_{k=0}^{i-1} \binom {t+m-1-i+k}{m-2} + \omega_{E'}(t-|\textbf{e}|) \\ ={}|\textbf{e}|\binom {t+m-1}{m-1} - \frac {|\textbf{e}|(|\textbf{e}|-1)}2 \binom {t+m-2}{m-2} +o(t^{m-2})+ \omega_{E'}(t-|\textbf{e}|). \end{align*}}$$
Поскольку $$\deg \omega_{E'}\leq m-2$$ (см. лемму 13.12), имеем $$a_{m-2}(E) = a_{m-2}(E') - \frac {|\textbf{e}|(|\textbf{e}|-1)}2$$, следовательно, можно вместо $$a_{m-2}(E)$$ вычислять $$a_{m-2}(E')$$, поэтому в дальнейших рассуждениях предполагаем, что $$\deg \omega_{E'}\leq m-2$$ и $$\omega_E(t) =\sum\limits_{i=0}^{m-2} a_i(E)\binom {t+i}i$$, где $$a_i(E) \in \Z$$ $$(i=0,1,\dots,m-2)$$. Кроме того, предполагаем, что $$E$$ содержит не более двух ненулевых столбцов (следует отметить, что если в $$E$$ имеется единственный ненулевой столбец, то многочлен Гильберта $$\omega_E(t)$$ совпадает с минимальным элементом этого столбца). Предполагая, что первый столбец матрицы $$E$$ ненулевой, упорядочим его элементы и применим (13.14) при $$\tau=m-2$$. Поскольку число столбцов в $$E_1$$ (см. (13.14)) равно $$(m-1)$$, вычисление $$a_\tau(E_1)$$ можно свести к выбору минимальных элементов в столбцах матрицы $$E_1$$ (см. теорему 12.8(3)). Легко видеть, что такой выбор требует $$(m-1)b_1$$ элементарных операций, где $$b_1$$ — число строк матрицы $$E_1$$. Применяя (13.14) к $$E_2$$, сводим вычисление $$a_\tau(E_2)$$ (в правой части формулы (13.14)) к вычислению коэффициента $$a_2(E_{21})$$ многочлена Гильберта некоторой матрицы $$E_2$$, содержащей $$(m-1)$$ столбец (эта матрица получена добавлением некоторых дополнительных строк к $$E_1$$ ). Чтобы вычислить $$a_\tau(E_{21})$$, нужно не более $$(m-1)b_2$$ элементарных операций (здесь $$b_2$$ обозначает число строк матрицы $$E_{21}$$ ). Продолжаем применять (13.14), пока не получим матрицу с нулевым первым столбцом. По лемме 13.17 такой столбец можно отбросить, затем применяем (13.14) к новой матрице и т. д.
Асимптотическая сложность $$g(n,m)$$ описанного алгоритма не превосходит$$\begin{multiline*} n\log n+\hskip-10pt\smash[t]{\sum\limits^k_{\substack{i=1\\b_i\in\mathbb N\\b_1+\dots+b_k=n}}}\hskip-10pt b_im+g(n,m-1)\\ \leq2n\log n+n(m+m-1)+g(n,m-2)\leq \dots\\ \leq(m-1)n\log n+n(m+(m-1)+\dots+2)+g(n,1)\\ =(m-1)n\log n+n\binom{m+1}2\sim mn\log n. \end{multiline*}$$
А14. АЛГОРИТМ $$(E, n,m, a_{m-2})$$.
$$\begin{equation}\\ \text{Дано:\quad $ n\in\mathbb N;\ m\in\mathbb N $ ; $ n\!\times\!m $ -матрица $ E $ , такая, что $ \deg \omega_E\leq m-2 $ }\\ \text{Надо:\qquad $ a_{m-2}(E) $ .}\\ \text{Начало}\\ \text{ $ a_{m-2}:=0$} \\ \text{ $ r:= $ число нулевых столбцов матрицы $ E$} \\ \text{ $ m:=m-r $}\\ \text{$ E: $ удалить нулевые столбцы }\\ \text{сортировать строки по возрастанию элементов первого столбца}\\ \text{$\mathbb N_S:=0 $ }\\ \text{ $ i:= 1$} \\ \text{ $ E_0:= \emptyset$} \\ \text{ цикл пока $ i <n$} \\ \text{\qquad цикл пока $ e_{i1}=N_S $ и $ i\leq n $ }\\ \text{\qquad \qquad $ E_0:=E_0\cup (e_{i2},\dots,e_{im}) $ }\\ \text{\qquad \qquad $ i := i + 1 $ }\\ \text{\qquad конец цикла}\\ \text{\qquad $ N_R := e_{i1} $ }\\ \text{\qquad $ \textbf{a} := (a_1,\dots,a_{m-1}) $ , где $ a_i $ - минимальный элемент $ i $ -го столбца} \\ \text{\qquad \quad матрицы, состоящей из векторов из $ E_0 $ }\\ \text{\qquad $ E_0:=\textbf{a} $ }\\ \text{\qquad $ a_{m-2}:= a_{m-2} + |\textbf{a}|(N_R - N_S) $ }\\ \text{\qquad $ N_S := N_R $ }\\ \text{конец цикла}\\ \text{ $ E: $ удалить первый столбец}\\ \text{алгоритм A14 $ (E,n,m-1,b) $ }\\ \text{ $ a_{m-2}:= a_{m-2}+ b $ }\\ \text{Конец}\\ \end{equation}$$Теперь, пользуясь алгоритмом A14 и формулой (13.14), можно
найти
А15. АЛГОРИТМ $$(E, n,m, k, a_{m-k})$$.
$$\begin{equation} \text{Дано:\qquad $ n\in\mathbb N $ , $ m\in\mathbb N $ , $ k\in\mathbb N $ , $ k\geq2 $ , $ m\geq k $;}\\ \text{\qquad $ n\!\times\!m $ -матрица $ E $ , такая, что $ \deg\omega_E\leq m-k $ }\\ \text{Надо: \qquad $ a_{m-k}(E) $ .}\\ \text{Начало}\\ \text{$ a_{m-k}:=0 $} \\ \text{$ r:= $ число нулевых столбцов матрицы $ E $} \\ \text{$ m:=m-r $ }\\ \text{$ E: $ удалить нулевые столбцы }\\ \text{сортировать строки по возрастанию элементов первого столбца}\\ \text{$mathbb N_S:=0 $} \\ \text{$ i:= 1 $} \\ \text{$ E_0:= \emptyset $} \\ \text{цикл пока $ i<n $} \\ \text{\qquad цикл пока $ e_{i1}=N_S $ и $ i\leq n $ }\\ \text{\qquad \qquad $ E_0:=E_0\cup (e_{i2},\dots,e_{im}) $} \\ \text{\qquad \qquad $ i := i + 1 $ }\\ \text{\qquad конец цикла}\\ \text{\qquad $ N_R := e_{i1} $ }\\ \text{\qquad $ \textbf{a} := (a_1,\dots,a_{m-1}) $ , где $ a_i $ - минимальный элемент $ i $ -го столбца }\\ \text{\qquad \quad матрицы, состоящей из векторов из $ E_0 $} \\ \text{\qquad $ E_0:=\textbf{a} $} \\ \text{\qquad $ a_{m-2}:= a_{m-2} + |\textbf{a}|(N_R - N_S) $ }\\ \text{\qquad $ N_S := N_R $ }\\ \text{конец цикла}\\ \text{$ E: $ удалить первый столбец}\\ \text{алгоритм А14 $ (E,n,m-1,b) $ }\\ \text{$ a_{m-2}:= a_{m-2}+ b $} \\ \text{если $ k=2 $ , то алгоритм А14 $ (E, n, m, a_{m-2) $} \\ \text{иначе $ E: $ удалить нулевые столбцы }\\ \text{\qquad $ m:= $ число столбцов матрицы $ E $} \\ \text{\qquad $ N_S := 0 $} \\ \text{\qquad $ E_0:=\emptyset $} \\ \text{\qquad цикл для каждого ненулевого $ e_{i1} $ в порядке возрастания }\\ \text{\qquad \qquad $ N_R:= e_{i1} $ }\\ \text{\qquad \qquad $ E_0: $ добавить последовательность строк}\\ \text{\qquad \qquad \qquad $ \{ (e_{j2},\dots,e_{jm})\mid e_{j1}= N_S\} $} \\ \text{\qquad \qquad $ N_0 := $ число векторов в $ E_0 $ }\\ \text{\qquad \qquad алгоритм А15 $ (E_0,N_0,m-1,k-1,P) $ }\\ \text{\qquad \qquad $ a_{m-k}:= a_{m-k}+ (N_R - N_S)P $ }\\ \text{\qquad \qquad $ N_S:= N_R $} \\ \text{\qquad конец цикла}\\ \text{\qquad $ E: $ удалить первый столбец}\\ \text{\qquad алгоритм А15 $ (E,n,m-1,k-1,P) $ }\\ \text{\qquad $ a_{m-k}:= a_{m-k}+ P $ }\\ \text{конец если}\\ \text{Конец}\\ \end{equation}$$Завершая изложение теории размерностных многочленов, следует упомянуть размерностные многочлены от многих переменных, теория которых была заложена в статье и подробно изложена в монографии .
В предыдущем параграфе (см.12.7) мы отмечали, что размерностный многочлен любого множества $$F\subseteq \N^m$$ равен размерностному многочлену, ассоциированному с множеством всех минимальных элементов множества $$F$$. Значит, достаточно уметь вычислять размерностные многочлены только для конечных множеств $$F\subseteq\N^m$$ (более того, можно предполагать, что элементы множества $$F$$ попарно несравнимы относительно порядка произведения).
Пусть $$E=(e_{ij})_{\substack{1\leq i\leq n\\ 1\leq j \leq m}}$$ обозначает $$n\!\times\! m$$ -матрицу над $$\mathbb N$$, т. е. матрицу с $$n$$ строками и $$m$$ столбцами, элементы которой - неотрицательные целые числа. Рассматривая строки матрицы $$E$$ как элементы множества $$\mathbb N^m$$ и обозначая $$i$$ -ю строку $$(e_{i1},\dots,e_{im})$$ через $$e_i$$ $$(1\leq i\leq n)$$, мы получим подмножество $$\tilde E=\{e_1,\dots,e_n\} \subseteq\mathbb N^m$$, ассоциированное с $$E$$. Напомним, что размерностный многочлен $$n\!\times\! m$$ -матрицы $$E$$ в точности совпадает с размерностным многочленом множества $$\tilde E$$ и называется многочленом Гильберта матрицы $$E$$.
Пусть $$\omega_E(t)$$ - размерностный многочлен $$n\!\times\!m$$ -матрицы $$E$$ над $$\mathbb N$$. По определению $$\omega_E(s)=Card V_E(s)$$ для всех достаточно больших $$s\in\mathbb N$$, где $$V_E$$ обозначает множество всех элементов из $$\mathbb N^m\setminus \tilde E$$, которые не превосходят ни одного элемента из $$\tilde E$$ относительно порядка произведения, так что $$v\in V_E$$ если и только если неравенство $$e_i\leq v$$ не выполняется ни для одного $$e_i$$ $$(1\leq i\leq n)$$.
Как было отмечено, для того, чтобы уметь вычислять размерностный многочлен любого подмножества в $$\mathbb N^m$$, достаточно уметь вычислять его для любой $$n\!\times\! m$$ -матрицы $$E$$ над $$\mathbb N$$. Один из методов вычисления основан на формуле (12,4).
Пусть $$E=(e_{ij})_{\substack{1\leq i\leq n\\ 1\leq j \leq m}}$$ обозначает $$n\!\times\!m$$ -матрицу над $$\mathbb N$$. Воспользуемся следующими обозначениями, введенными в параграфе 12:$$\textbf{e}_\xi=\begin{cases} (0,\dots,0) \text{если } \xi=\emptyset,\\ (e_1=\max_{i\in\xi}\{ e_{i1}\} ,\dots,e_m= \max_{i\in\xi}\{ e_{im}\} ) \text{если } \xi\neq \emptyset \end{cases}$$ для любого подмножества $$\xi\subseteq\mathbb N_n$$ и $$|\textbf{e}_\xi|=\smash{\sum\limits_{j=1}^m}e_j$$. По предложению 12.9 (см. 12.4) мы можем записать$$\omega_E(t) = \binom {t+m}m +\sum_{l=1}^n(-1)^l \sum_{\xi\in A(l,n)}\binom{t+m-|\textbf{e}_\xi|}m,$$ где $$A(l,n)$$ $$(1\leq l\leq n)$$ обозначает множество всех $$l$$ -элементных подмножеств множества $$\mathbb N_n=\{1,\dots,n\}$$.
Пользуясь выписанной формулой, можно предложить следующий алгоритм вычисления размерностного многочлена $$\omega_E(t)$$, ассоциированного с $$n\!\times\! m$$ -матрицей $$E$$.
А9. АЛГОРИТМ $$(E, n, m, \omega)$$.
$$ \text{Дано: $n \in \mathbb N ; m \in \mathbb N ; n \times m$-матрица E}.\\ \text{Надо: $\omega_E(t)$ — многочлен Гильберта матрицы $E$.}\\ \text{Переменные: $IB$ — вектор типа $true/false$ с индексами $1..n$;}\\ \text{\qquad \qquad $\textbf{v} = (v1, . . . , vm)$ — вектор типа $N$ с индексами $1..m$;}\\ \text{\qquad \qquad $S_1$ — переменная типа $\pm 1$;}\\ \text{\qquad \qquad $S_2$ — переменная типа $ \mathbb N $.}\\ \text{Начало}\\ \text{$\omega(t) := \binom {t+m}m$}\\ \text{цикл для $m$ каждого вектора $IB$}\\ \text{\qquad $v := (0, . . . , 0)$}\\ \text{\qquad $S_1 := 1$}\\ \text{\qquad цикл для $j$ от $1$ до $n$}\\ \text{\qquad \qquad если $IB(j)$ то}\\ \text{\qquad \qquad \qquad $\textbf{v} := НОК(\textbf{v}, \textbf{e}_j)$}\\ \text{\qquad \qquad \qquad $S_1 := -S_1$}\\ \text{\qquad \qquad конец если}\\ \text{\qquad \qquad $S_2 := \textbf{v}_1 + \dots + \textbf{v}_m$}\\ \text{\qquad \qquad $\omega(t) := \omega(t) + S_1\binom {t+m-S_2}m$}\\ \text{\qquad конец цикла} \\ \text{конец цикла}\\ \text{Конец}\\ $$Легко видеть, что асимптотическая сложность алгоритма A9 имеет порядок $$n\!\times\! 2^n$$, где $$n$$ - число строк матрицы $$E$$ (по теореме 12.8 мы можем считать, что строки попарно несравнимы относительно порядка произведения на $$\mathbb N^m$$ ).
Мора и Меллер модифицировали алгоритм вычисления многочлена Гильберта . Их алгоритм основан на следующих соображениях. Легко видеть, что в формуле (12.5) может выполняться равенство $$\textbf{e}_\xi=\textbf{e}_\theta$$ для двух различных подмножеств $$\xi$$ и $$\theta$$ множества $$\mathbb N_n$$, таких, что $$Card\xi$$ и $$Card\theta$$ являются четным и нечетным числами соответственно (мы пользуемся обозначениями предложения 12.9). Тогда соответствующие слагаемые в формуле (12.5) сократятся. Более того, можно сгруппировать все слагаемые, соответствующие одному и тому же элементу $$\tau \in\mathbb N^m$$.
Пусть $$T=T(E)$$ - множество всех элементов $$\tau\in\mathbb N^m$$, которые равны, по крайней мере, одному из элементов $$\textbf{e}_\xi$$, где $$\xi\subseteq\mathbb N_n$$. Тогда из формулы (12.4) следует, что$$ \omega_E(t) =\sum_{\tau\in T}\sum_{k=0}^n(-1)^k\sum_{\{\xi\in A(k,n)\mid \textbf{e}_\xi=\tau\} } \binom {t+m-|\tau|}m\\ =\sum_{\tau\in T} \mu_\tau \binom {t+m-|\tau|}m,\ $$ где $$|\tau|$$ обозначает сумму всех координат вектора $$\tau$$, и$$\begin{equation} \mu_\tau=\sum\limits_{k=0}^n\sum\limits_{\substack{ \xi\in A(k,n)\\\textbf{e}_\xi=\tau} }(-1)^k. \end{equation}$$
Очевидно, если матрица $$E_1$$ получена присоединением строки $$\textbf{e} = (e_1,\dots,e_m)$$ к матрице $$E$$, $$T_1= T(E_1)$$ и $$\{\mu'_\tau|\tau \in T_1\}$$ - множество коэффициентов (13.2) в соотношении (13.1) для многочлена $$\omega_{E_1}(t)$$, так что$$\mu'_\tau= \sum_{k=0}^{n+1}\sum_{\substack{ \xi\in A(k,n+1)\\\textbf{e}_\xi=\tau} }(-1)^k$$ для каждого $$\tau \in T_1$$, то$$\begin{equation} \mu'_\tau=\begin{cases} \mu_\tau-\sum_{\{ u\in T\mid HOK (u,\textbf{e})=\tau\} }\mu_{u} \text{ если } \tau\in T\\ -\sum_{\{ u\in T\mid HOK (u,\textbf{e})=\tau\} }\mu_{u} \text { если } \tau\in T_1\setminus T \end{cases} \end{equation}$$
Таким образом, вычисление многочлена $$\omega_E(t)$$, т. е. вычисление коэффициентов $$\mu_\tau\ (\tau \in T)$$, в (13.1) может быть основано на формуле (13.3), если мы начнем с пустой матрицы (число строк которой равно нулю и многочлен Гильберта которой равен $$\binom {t+m}m$$ ) и последовательно будем присоединять строки матрицы $$E$$, вычисляя множество $$T$$ и коэффициенты $$\mu_\tau$$ $$(\tau \in T)$$ на каждом шаге (см. алгоритм A10 ).
$$ \text{Дано: $n \in \mathbb N ; n \times m$-матрица E}.\\ \text{Надо: $\omega_E(t)$ — многочлен Гильберта матрицы $E$.}\\ \text{Переменные: $T,\; T_1$ —множества типа}\\ \text{\qquad \qquad \qquad \qquad $\{$вектор типа $ \mathbb N $ с индексами $1..m\}$};\\ \text{\qquad \qquad \qquad $\mu, \mu_1$ —векторы типа $ \mathbb Z $ с индексами из $T, T_1$.}\\ \text{Начало}\\ \text{$\omega:= 0$}\\ \text{$T:=\{(0, \dots , 0)\}$}\\ \text{$\mu (0, \dots , 0):=1$}\\ \text{цикл для $i$ от $1$ до $n$}\\ \text{\qquad $T_1:=T$}\\ \text{\qquad цикл для каждого $u \in T_1$}\\ \text{\qquad \qquad $\mu_1(\textbf{u}):=\mu(\textbf{u})$}\\ \text{\qquad конец цикла}\\ \text{\qquad цикл для каждого $u \in T_1$}\\ \text{\qquad \qquad $\tau := НОК(\textbf{u}, ei), e_i —i$-я строка матрицы $E$}\\ \text{\qquad \qquad если $\tau \in T$ то}\\ \text{\qquad \qquad \qquad $\mu(\tau ) := \mu(\tau ) - \mu_1(\textbf{u})$}\\ \text{\qquad \qquad иначе $T := T \cup \tau ; \mu(\tau ) := -\mu_1(\textbf{u})$}\\ \text{\qquad \qquad конец если}\\ \text{\qquad конец цикла}\\ \text{конец цикла}\\ \text{цикл для каждого $\textbf{u} \in T$}\\ \text{\qquad $\omega (t):= \omega (t) + \mu(\textbf{u})\binom {t+m-|\textbf{u}|}m$}\\ \text{конец цикла}\\ \text{Конец}\\ $$Поскольку на $$k$$ -м шаге $$(1\leq k\leq n)$$ алгоритма каждый элемент $$\textbf{u} \in T_1$$ является наименьшим общим кратным некоторого подмножества множества $$\{\textbf{e}_1,\dots,\textbf{e}_{k-1}\}$$ (т. е. $$\textbf{u}=\textbf{e}_\xi$$ для некоторого $$\xi\subseteq \mathbb N_{k-1}$$ ), существует не более $$(k-1)$$ различных возможностей для выбора каждой координаты вектора $$\textbf{u}$$, следовательно, на $$k$$ -м шаге $$(1\leq k\leq n)$$ множество $$T_1$$ содержит не более $$(k-1)^m$$ элементов. Вычисление всех элементов $$\tau=HOK(\textbf{u},\textbf{e}_k)$$ требует не более $$m(k-1)^m$$ сравнений, и можно предполагать (используя достаточно эффективный метод сортировки), что число проверок на принадлежность $$\tau\in T$$ не превосходит $$k^m\log k$$ для всех достаточно больших $$k \in \mathbb N$$. Таким образом, асимптотическая сложность (по $$n$$ ) алгоритма A10 не превосходит $$m\sum\limits_{k=2}^n\left[(k-1)^m+k^m\log k\right]$$. Поскольку $$m \sum\limits_{k=2}^n\left[ (k - 1)^m+ k^m\log k\right] < 2m \sum\limits_{k=2}^n k^m \log k$$, асимптотическая сложность имеет порядок $$n^{m+1}\log n$$.
Следующие алгоритмы вычисления размерностного многочлена произвольной $$n\!\times\! m$$ -матрицы $$E$$ сводят эту задачу к аналогичной задаче для матрицы с числом строк меньшим, чем в $$E$$. По одному из этих алгоритмов (см. ниже алгоритм A11 ) можно вычислить коэффициенты $$\mu_\tau$$ в (13.1) размерностного многочлена $$\omega_E(t)$$, что дает выражение для размерностного многочлена. Для обоснования этого алгоритма нам нужны некоторые свойства коэффициентов $$\mu_\tau$$, которые сформулированы ниже в леммах 13.1-13.5, 13.7 и 13,9. Последняя из этих лемм устанавливает соотношения, на которых основан алгоритм вычисления $$\mu_\tau$$.
Чтобы подчеркнуть зависимость коэффициентов $$\mu_\tau$$ от матрицы $$E$$, будем обозначать эти коэффициенты $$\mu_\tau (E)$$ и продолжим это обозначение на случай произвольного вектора $$\tau \in \mathbb N^m$$, полагая$$\mu_\tau(E) =\begin{cases} \mu_\tau, \text {если } \tau\in T\\ 0, \text {если } \tau\in\mathbb N^m\setminus T.\end{cases}$$ (Напомним, что $$T=T(E)$$ - множество всех элементов $$\tau\in\mathbb N^m$$, таких, что каждый $$\tau$$ равен либо $$(0,\dots,0)$$, либо наименьшему общему кратному некоторых строк матрицы $$E$$ ; элементы множества $$T$$ будем называть допустимыми элементами или допустимыми векторами матрицы $$E$$.)
13.1. ЛЕММА. Пусть дана $$n\!\times\! m$$ -матрица$$E = (e_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}.$$ Предположим, что элемент $$\tau =(\tau_1,\dots,\tau_m) \in \mathbb N^m$$ мажорирует все строки этой матрицы, т. е. $$\tau$$ больше любой строки матрицы $$E$$ или равен ей (относительно порядка произведений на $$\mathbb N^m$$ ). Тогда $$\mu_\tau(E) = \mu_{(1,\dots,1)}(H)$$, где $$H = (h_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$$ - матрица с элементами$$h_{ij}=\begin{cases} 1, \text {если } e_{ij}=\tau_j,\\ 0, \text {если } e_{ij}\neq \tau_j,\end{cases}$$ $$(i=1,\dots,n)$$.
ДОКАЗАТЕЛЬСТВО. Пусть $$\xi=\{ i_1,\dots,i_k\}\in A(k, n)$$ $$(1\leq k\leq n)$$, $$\textbf{e}_\xi=НОК \{\textbf{e}_{i_1},\dots,\textbf{e}_{i_k}\}$$ и $$\textbf{h}_\xi =НОК \{\textbf{h}_{i_1},\dots,\textbf{h}_{i_k}\}$$ ( $$\textbf{e}_i$$ и $$\textbf{h}_i$$ обозначают $$i$$ -е строки матриц $$E$$ и $$H$$ соответственно). Покажем, что равенство $$\textbf{e}_\xi=\tau$$ эквивалентно равенству $$\textbf{h}_\xi=(1,\dots,1)$$. Действительно, если $$\textbf{e}_\xi = \tau$$, то $$\tau_j= \max \{ e_{i_1j},\dots,e_{i_kj}\}$$ $$(1\leq j\leq m)$$, так что для каждого $$j=1,\dots,m$$ существует индекс $$\lambda (j)\in\mathbb N_k$$, такой, что $$h_{i_{\lambda (j)}}=1$$. Таким образом, $$j$$ -й элемент строки $$\textbf{h}_{i_{\lambda (j)}}$$ равен 1, следовательно, $$\textbf{h}_\xi =НОК \{\textbf{h}_{i_1},\dots,\textbf{h}_{i_k}\} = (1,\dots,1)$$. Обратно, если $$\textbf{h}_\xi= (1,\dots,1)$$, то для каждого $$j=1,\dots,m$$ существует число $$\nu =\nu(j)\in\mathbb N_k$$, такое, что $$h_{i_\nu j}=\max_{i\in\xi}\{ h_{ij}\} = 1$$, т. е. $$e_{i_\nu j} = \tau_j$$. Поэтому, $$\textbf{e}_\xi\geq\tau$$, следовательно, $$\textbf{e}_\xi= \tau$$ (так как элемент $$\tau$$ больше любой строки матрицы $$E$$ или равен ей). Таким образом,$$\mu_\tau =\sum\limits_{k=0}^n\sum\limits_{\substack{ \xi\in A(k,n)\\ \textbf{e}_\xi=\tau}} (-1)^k= \sum\limits_{k=0}^n\sum\limits_{\substack{ \xi\in A(k,n)\\ \textbf{h}_\xi=(1,\dots,1)}} (-1)^k=\mu_{(1,\dots,1)}(H). \eqno{\text{\qedsymbol}}$$
Рассмотрим свойства размерностных многочленов матриц, состоящих из 0 и 1
(такова, например, матрица $$H$$ в лемме
13.1). Длякраткости будем писать $$\mu_1(E)$$
вместо $$\mu_{(1,\dots,1)}(E)$$, где $$E$$ - $$n\!\times\! m$$ -матрица и $$(1,\dots,1) \in \mathbb N^m$$.
13.2. ЛЕММА. Пусть $$E$$ - $$n\!\times\! m$$ -матрица, состоящая из 0 и 1, и $$\omega_E(t)$$ - ее многочлен Гильберта. Тогда $$\mu_1(E) = (-1)^m\omega_E(-1)$$.
ДОКАЗАТЕЛЬСТВО.
По (12.4) имеем$$\begin{equation} \omega_E(t) =\sum_{\tau\in T}\mu_\tau\binom {t+m-|\tau|}m,
\end{equation}$$
и, очевидно, каждая координата любого вектора$$\tau =
(\tau_1,\dots,\tau_m) \in T=T(E)$$
равна либо 0, либо 1. Если $$\tau \neq (1,\dots,1)$$, то $$0 \leq
|\tau|= \sum\limits_{i=1}^m\tau_i < m$$. В этом случае
многочлен $$\binom {t+m-|\tau|}m$$ обращается в нуль при $$t=-1$$, следовательно,$$\begin{align*}
\omega_E(-1) = \mu_1(E)\left. \binom {t+m-|\tau|}m\right|_{t=-1} \\
= \mu_1(E)\left. \frac {t(t-1)\dots(t-m+1)}{m!}
\right|_{t=-1} \\
=(-1)^m \mu_1(E). \tag*{\qedsymbol}
\end{align*}$$
Из леммы 13.2 следует, что$$\begin{equation} \mu_1(E) = (-1)^m \omega_E(-1), \end{equation}$$ где $$\omega_E(t)$$ - многочлен Гильберта матрицы $$E$$. Если$$\omega_E(t)=\sum\limits_{i=0}^m a_i\binom {t+i}i \quad (a_0,a_1,\dots,a_m \in \mathbb Z),$$ то $$\omega_E(-1)=a_0$$, так что $$\mu_1(E)$$ равно свободному члену многочлена Гильберта $$\omega_E(t)$$.
13.3. ЛЕММА. Пусть $$E$$ - $$n\!\times\! m$$ -матрица, состоящая из 0 и 1. Тогда
ДОКАЗАТЕЛЬСТВО. Все утверждения леммы следуют из (13.5) и из доказанных выше свойств размерностного многочлена матрицы $$E$$.
(1) Если $$E$$ содержит нулевую строку, то $$\omega_E(t)\equiv 0$$ (см. теорему 12.8(6). Применяя лемму 13.2, получаем $$\mu_1(E)=0$$.
(2) Если каждый элемент $$\nu$$ -го столбца матрицы $$E$$ равен нулю $$(1\leq \nu \leq m)$$, то из формулы (13.2) следует, что $$\mu_1(E)=0$$ (действительно, в обозначениях формулы (13.2) $$\nu$$ -ая координата любого вектора $$\textbf{e}_\xi$$ $$(\xi \subseteq \mathbb N_m)$$ равна нулю, так что $$\textbf{e}_\xi\neq (1,\dots,1)$$ ни для какого подмножества $$\xi \subseteq \mathbb N_m$$ ).
(3) Очевидно, что перестановка строк (или столбцов) матрицы $$E$$ не меняет значения $$\omega_E(t)$$, а, значит, и значения $$\mu_1(E)= (-1)^m \omega_E(-1)$$ (см. утверждения (3) и (4) теоремы 12.8).
(4) Пусть $$E$$ состоит из одной строки $$\textbf{e}=(1,\dots,1)$$. Поскольку$$\begin{multiline*} V_{\textbf{e}}(s)=Card\mathbb N^m(s)\\ -Card\{(1+u_1,\dots,1+u_m)\mid (u_1,\dots,u_m) \in\mathbb N^m(s - m)\} \\ = \binom {s+m}m-\binom sm \end{multiline*}$$ для всех достаточно больших $$s\in\mathbb N$$, имеем$$\omega_E(t) = \binom {t+m}m-\binom tm = \frac {(t+1)\dots(t+m)}{m!} - \frac {t(t-1)\dots(t-m+1)}{m!}.$$ Значит, $$\mu_1(E) = (-1)^m\omega_E(-1) = (-1)^m(-1)^{m+1}= -1$$.
(5) По теореме 12.8(8) имеем $$\omega_E(t) \equiv \omega_H(t)$$, следовательно, $$\mu_1(E) =(-1)^m\omega_E(-1) = -(-1)^{m-1}\omega_H(-1) = -\mu_1(H)$$.
Пусть $$E = (e_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$$ - $$n\!\times\! m$$ -матрица над $$\mathbb N$$, $$\tilde E=\{\textbf{e}_1,\dots,\textbf{e}_n\}$$ - множество строк матрицы $$E$$ и $$\textbf{e}=(e_1,\dots,e_m)$$ - элемент множества $$\mathbb N^m$$. Пусть $$E\cup\textbf{e}$$ обозначает $$(n+1)\!\times\! m$$ -матрицу, полученную присоединением строки $$\textbf{e}$$ к матрице $$E$$ (без потери общности можно предполагать, что $$\textbf{e}$$ является $$(n+1)$$ -й строкой матрицы $$E\cup\textbf{e}$$ ). Следующая лемма устанавливает связь между размерностными многочленами матриц $$E$$ и $$E\cup\textbf{e}$$. Как и выше, $$|E|$$ обозначает сумму $$\sum\limits_{i=1}^n\sum\limits_{j=1}^me_{ij}$$ всех элементов матрицы $$E$$ (в частности, $$|\textbf{e}|$$ обозначает сумму всех координат элемента $$\textbf{e}\in\mathbb N^m$$ ).
13.4. ЛЕММА. Пусть $$E$$ является $$n\!\times\! m$$ -матрицей $$(n,m\in\mathbb N$$ ; $$m>1$$, $$n\geq 1)$$, состоящей из нулей и единиц. Если первый столбец матрицы $$E$$ состоит только из нулей, а матрица $$E_1$$ получена из $$E$$ удалением этого нулевого столбца, то $$\omega_E(-2)=-\omega_{E_1}(-1)$$.
ДОКАЗАТЕЛЬСТВО. Применяя формулу (12.2) к матрице $$E$$ и вектору $$\textbf{e}=(1,0,\dots,0)$$, получим $$\omega_E(t) = \omega_{E\cup\textbf{e}}(t) + \omega_H(t-1)$$, где $$H = (h_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$$ - матрица с элементами $$h_{ij}=\max \{e_{ij}- e_j,0\}$$ ( $$e_1= 1,\ e_2=0,\dots,e_m= 0$$ суть координаты вектора $$\textbf{e}$$ ). Очевидно, $$H=E$$ и $$\omega_{E\cup\textbf{e}}(t) =\omega_{E_1}(t)$$ (см. теорему 12.8(8)), так что $$\omega_E(t)= \omega_{E_1}(t)+\omega_E(t-1)$$ и, в частности, $$\omega_{E_1}(-1) + \omega_E(-2) = \omega_E(-1)$$. Поскольку $$E$$ содержит нулевой столбец, из леммы 13.3(2) следует, что $$\omega_E(-1) = (-1)^m\mu_1(E) = 0$$, значит, $$\omega_E(-2) = -\omega_{E_1}(-1)$$.
13.5. ЛЕММА. Пусть $$E = (e_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$$ $$(n,m\in\mathbb N$$ ; $$m>1$$, $$n\geq 1)$$ является $$n\!\times\! m$$ -матрицей состоящей из нулей и единиц. Предположим, что $$e_{j1}=1$$ для $$j=1,\dots,r$$ и $$e_{j1}=0$$ для $$j=r+1,\dots,n$$ $$(1\leq r\leq n)$$. Тогда $$\mu_1(E)= \mu_1(E_1) - \mu_1(E_2)$$, где матрица $$E_1$$ получена из $$E$$ удалением первого столбца, а $$E_2$$ получена из $$E_1$$ удалением $$r$$ первых строк.
ДОКАЗАТЕЛЬСТВО. Применяя (12.2) к $$E$$ и $$\textbf{e}= (1,0,\dots,0)$$, получаем $$\omega_E(t) = \omega_{E\cup \textbf{e}}(t) + \omega_H(t-1)$$, где $$H= (h_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$$ - $$n\!\times\! m$$ -матрица с элементами$$h_{ij}=\max \{ e_{ij}- e_j,0\} = \begin{cases} 0, \kern-7pt\text {если } j=1,\\ e_{ij}, \kern-7pt\text {если } j\neq 1.\end{cases}$$ По теореме 12.8(8) $$\omega_{E\cup\textbf{e}}(t) = \omega_{E_2}(t)$$, следовательно, $$\omega_E(t) = \omega_{E_2}(t) + \omega_H(t-1)$$. Далее, пользуясь леммой 13.4, можно написать $$\omega_H(-2) = -\omega_{E_1}(-1)$$, значит, $$\omega_E(-1) = \omega_{E_2}(-1) - \omega_{E_1}(-1)$$. Теперь, по лемме 13.2 имеем$$\begin{multiline*} \mu_1(E) = (-1)^m\omega_E(-1) = (-1)^m\omega_{E_2}(-1) + (-1)^{m-1}\omega_{E_1}(-1) \\ = \mu_1(E_1) - \mu_1(E_2). \tag*{\qedsymbol} \end{multiline*}$$
13.6. СЛЕДСТВИЕ. Пусть
$$E =(e_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$$ $$(m,n\in\mathbb N,\ m>1)$$ - $$n\!\times\! m$$ -матрица, состоящая из 0 и 1. Предположим, что существуют $$p,q\in\mathbb N_m$$, такие, что $$e_{ip}\geq e_{iq}$$ для всех $$i=1,\dots,n$$. Тогда $$\mu_1(E) = \mu_1(E_1)$$, где $$E_1$$ получена из $$E$$ удалением $$p$$ -го столбца.
ДОКАЗАТЕЛЬСТВО. Поскольку размерностный многочлен матрицы $$E$$ инвариантен относительно перестановок строк (или столбцов) матрицы $$E$$, значение $$\mu_1(E) = (-1)^m \omega_E(-1)$$ также обладает этим свойством. Поэтому, без потери общности, можно считать, что $$p=1$$ и существует $$r\in\mathbb N_{n-1}$$, такое, что $$e_{j1}= 1$$ для $$j = 1,\dots,r$$, и $$e_{j1}= 0$$ для $$j = r+1,\dots,n$$. По лемме 13.5, $$\mu_1(E) =\mu_1(E_1)-\mu_1(E_2)$$, где $$E_2$$ получена из $$E$$ удалением первого столбца и $$r$$ первых строк (поскольку $$0\leq e_{iq}\leq e_{i1}=0$$ для $$i=r+1,\dots,n$$, каждый элемент $$q$$ -го столбца матрицы $$E_2$$ равен нулю). Следовательно, $$\mu_1(E_2)=0$$ (см. лемму 13.3(2)), так что $$\mu_1(E)=\mu_1(E_1)$$.
13.7. ЛЕММА. Пусть
$$E =(e_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$$ $$(m,n\in\mathbb N,\ m>1)$$ - $$n\!\times\! m$$ -матрица, состоящая из 0 и 1. Предположим, чт о $$E$$ содержит строку $$\textbf{e}=(e_1,\dots,e_m)$$, такую, что $$e_i=1$$ для $$1\leq i\leq r$$ и $$e_i= 0$$ для $$r<i\leq m$$ $$(r \in \mathbb N_{m-1})$$. Тогда $$\mu_1(E) = \mu_1(E\setminus \textbf{e}) - \mu_1(E_1)$$, где матрица $$E\setminus \textbf{e}$$ получена удалением строки $$\textbf{e}$$ из матрицы $$E$$, а $$(n-1)\!\times\! (m-r)$$ - матрица $$E_1$$ получена из матрицы $$E\setminus \textbf{e}$$ удалением $$r$$ первых столбцов.
ДОКАЗАТЕЛЬСТВО. Применяя формулу (12.3) к матрице $$E$$ и строке $$\textbf{e}=(1,\dots,1,0,\dots,0)$$, получаем $$\omega_E(t) = \omega_{E\setminus \textbf{e}}(t) - \omega_{\tilde E_1}(t-r)$$, где матрица $$\tilde E_1$$ получена из $$E_1$$ присоединением слева $$r$$ нулевых столбцов. Теперь из (12.2) видно, что $$\omega_{\tilde E_1}(t) = \omega_{\tilde E_1\cup\textbf{e}}(t) + \omega_{\tilde E_1}(t-r)$$, следовательно,$$\omega_E(-1) = \omega_{E\setminus \textbf{e}}(-1) - \omega_{\tilde E_1}(-1-r) = \omega_{E\setminus \textbf{e}}(-1) + \omega_{\tilde E_1\cup\textbf{e}}(-1)-\omega_{\tilde E_1}(-1).$$
Поскольку $$\tilde E_1$$ содержит нулевой столбец, из пункта 2 леммы 13.3 следует, что $$\mu_1(\tilde E_1) = 0$$, значит,$$\omega_{\tilde E_1}(-1) = (-1)^m\mu_1(\tilde E_1) = 0$$ (см. лемму 13.2) и$$\begin{align*} \mu_1(E)= (-1)^m\omega_E(-1) = (-1)^m\omega_{E\setminus \textbf{e}}(-1) + (-1)^m \omega_{\tilde E_1\cup\textbf{e}}(-1)\\ =\mu_1(E\setminus\textbf{e})+\mu_1(\tilde E_1\cup \textbf{e}). \end{align*}$$ Поскольку каждый из первых $$(r-1)$$ столбцов матрицы $$\tilde E_1\cup \textbf{e}$$ мажорирует $$r$$ -й столбец этой матрицы, из следствия 13.6 вытекает, что $$\mu_1(\tilde E_1\cup \textbf{e})= \mu_1({\mathbf0}E_1\cup (1,0,\dots,0))$$, где $${\mathbf0}E_1$$ - матрица, полученная присоединением слева нулевого столбца к $$E_1$$. Применяя теперь п.5 леммы 13.3, получаем $$\mu_1({\mathbf0 E_1\cup(1,0,\dots,0)) =-\mu_1(E_1)$$, откуда следует требуемое соотношение $$\mu_1(E)=\mu_1(E\setminus\textbf{e})-\mu_1(E_1)$$.
Пусть
$$E = (e_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$$ - $$n\!\times\! m$$ -матрица. По теореме 12.8 п.5, удаление "лишних" строк матрицы $$E$$ не меняет размерностный многочлен этой матрицы, значит, не меняет и значение $$\mu_1(E)$$. Кроме того, если любой элемент матрицы $$E$$ равен либо 0, либо 1, то из следствия 13.6 вытекает, что удаление "лишних" столбцов матрицы $$E$$ не меняет значения $$\mu_1(E)$$ ( $$p$$ -й столбец матрицы $$E = (e_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$$ $$(1\leq p\leq m)$$ называется "лишним", если существует число $$q \in \mathbb N_m$$, такое, что $$q \neq p$$ и $$e_{ip}\geq e_{iq}$$ для всех $$i=1,\dots,n $$ ).
Таким образом, в ходе вычисления $$\mu_1(E)$$ (где $$E$$ - $$n\!\times\! m$$ -матрица, состоящая из 0 и 1) мы можем прежде всего отбросить "лишние" строки и столбцы (по п.5 леммы 13.3, эти вычисления сопровождаются соответствующими изменениями знака $$\mu_1(E)$$ ), а затем отбросить строки и столбцы, удовлетворяющие соотношениям леммы 13.5. Затем мы можем выбрать одну из следующих альтернатив: воспользоваться леммой 13.5 для вычисления $$\mu_1(E_1)$$ (где $$E_1$$ - матрица, полученная из $$E$$ с помощью описанного выше процесса сокращения) или вычислить $$\mu_1(E_1)$$, воспользовавшись леммой 13.7, т. е. "раскладывая" $$E_1$$ по строкам и столбцам соответственно. Очевидно, что если число строк матрицы $$E_1$$ больше числа ее столбцов, то предпочтительнее "движение по столбцам" с помощью леммы 13.5, в противном случае для вычисления $$\mu_1(E_1)$$ целесообразно воспользоваться леммой 13.7.
13.8. ПРИМЕР. Найдем значение $$\mu_1(E)$$ для матрицы$$E=\left(\smallmatrix 0011\\ 0101\\0110\\1001\\1010\\1100 \endsmallmatrix\right).$$ Применяя лемму 13.5, получаем $$\mu_1(E) = \mu_1(E_1) - \mu_1(E_2)$$, где$$E_1 =\left(\smallmatrix 011\\ 101\\110\\001\\010\\100 \endsmallmatrix\right),$$ $$E_2=\left(\smallmatrix 011\\ 101\\110 \endsmallmatrix\right).$$ Легко видеть, что три первых строки матрицы $$E_1$$ являются "лишними", поэтому$$\mu_1(E_1) = \mu_1\left(\left(\smallmatrix 001\\ 010\\100 \endsmallmatrix\right)\right)=-1$$ (см. п.5 леммы 13.3). Применяя еще раз лемму 13.5, получаем (в силу утверждений леммы 13.3, что $$\mu_1(E_2) = \mu_1\left(\left(\smallmatrix 11\\ 01\\10 \endsmallmatrix\right)\right)-\mu_1((1,1))=1+1=2.$$ Следовательно, $$\mu_1(E) = \mu_1(E_1) - \mu_1(E_2) = -3$$.
Другой метод вычисления $$\mu_1(E)$$ основан на лемме 13.7:$$\begin{align*} \mu_1(E)= \mu_1\left(\left(\smallmatrix 0101\\ 0110\\1001\\1010\\1100 \endsmallmatrix\right)\right) - \mu_1\left(\left(\smallmatrix 01\\ 01\\ 10\\10\\11\endsmallmatrix\right)\right) \\ =\mu_1\left(\left(\smallmatrix 0110\\1001\\1010\\1100 \endsmallmatrix\right)\right)- \mu_1\left(\left(\smallmatrix 01\\10\\10 \endsmallmatrix\right)\right)- 1\\ =\mu_1\left(\left(\smallmatrix 1001\\1010\\1100 \endsmallmatrix\right)\right)- \mu_1\left(\left(\smallmatrix 11\\10\\10 \endsmallmatrix\right)\right) - 2\\ =\mu_1\left(\left(\smallmatrix 1010\\1100 \endsmallmatrix\right)\right)- \mu_1\left(\left(\smallmatrix 01\\ 10 \endsmallmatrix\right)\right) - 2=-3. \end{align*}$$
В качестве следствия леммы 13.7 получаем следующее утверждение, на котором основан алгоритм вычисления размерностного многочлена матрицы (см. ниже алгоритм A11 ).
13.9. ЛЕММА. Пусть $$E = (e_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$$ - $$n\!\times\! m$$ -матрица над $$\mathbb N$$ и $$\tau = (\tau_1,\dots,\tau_m) \in T = T(E)$$ (как и выше, $$T(E)$$ обозначает множество всех допустимых векторов матрицы $$E$$, т. е. множество всех элементов $$\tau \in \mathbb N^m$$, равных либо $$(0,\dots,0)$$, либо наименьшему общему кратному некоторых строк матрицы $$E$$ ). Пусть $$K$$ - матрица, состоящая из всех тех строк матрицы $$E$$, которые мажорируются вектором $$\tau$$ (для определенности предположим, что строки матрицы $$K$$ располагаются в том же порядке, в каком они расположены в матрице $$E$$ ). Кроме того, пусть $$\mbk = (k_1,\dots,k_m)$$ - одна из строк матрицы $$K$$ и $$K\setminus\mbk$$ - матрица, полученная удалением строки $$\mbk$$ из $$K$$. Тогда для любого подмножества $$J =\{ i_1,\dots,i_l\} $$ множества $$\mathbb N_m$$, такого, что $$i_1<\dots<i_l\ (1\leq l\leq m)$$, имеем$$\begin{equation} \mu_\tau (K,m) = \mu_\tau (K\setminus\mbk,m) - \mu_{\tau'} (K\setminus\mbk,J), \end{equation}$$ где $$\mu_\tau (K,m)$$, $$\mu_\tau(K\setminus\mbk,m)$$ суть соответственно коэффициенты $$\mu_\tau$$, определенные формулой (13.2) для матриц $$K$$ и $$K\setminus\mbk$$, а $$\mu_{\tau'}(K\setminus\mbk,J)$$ - аналогичные коэффициенты для вектора $$\tau'=(\tau_{i_1},\dots,\tau_{i_l})\in\mathbb N^l$$ (вместо $$\tau$$ ) и для $$(n-1)\!\times\!(m-l)$$ -матрицы, полученной из $$E$$ удалением столбцов с индексами $$j\in\mathbb N_m\setminus J$$.
ДОКАЗАТЕЛЬСТВО. Без потери общности можно предположить, что $$\mbk$$ - первая строка матрицы $$K$$. Из леммы 13.1 следует, что$$\mu_\tau(K,m) = \mu_1(H)$$ , где $$H= (h_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$$ - $$n\!\times\! m$$ -матрица с элементами $$h_{ij}=\begin{cases} 1, \text {если } e_{ij}= \tau_j,\\ 0, \text {если } e_{ij}\neq\tau_j,\end{cases}$$ $$(i = 1,\dots,n)$$. Аналогично, $$\mu_\tau(K\setminus\mbk,m) = \mu_1(H_1)$$ и $$\mu_{\tau'}(K\setminus\mbk,J) = \mu_1(H_2)$$, где матрица $$H_1$$ получена из $$H$$ отбрасыванием первой строки, а $$H_2$$ получена из $$H_1$$ отбрасыванием столбцов с индексами $$i_1,\dots,i_l$$. Применяя теперь лемму 13.7, получаем соотношение $$\mu_1(H) = \mu_1(H_1) - \mu_1(H_2)$$, из которого следует требуемое утверждение.
Вычисление коэффициентов $$\mu_\tau$$ $$(\tau \in T = T(E))$$ в (13.4) для размерностного многочлена произвольной $$n\!\times\! m$$ -матрицы $$E$$ (а, значит, и вычисление самого размерностного многочлена) может быть выполнено по следующей схеме: сначала применяем (13.6) к матрице $$E$$ (формируя матрицу $$K$$ тех строк матрицы $$E$$, которые мажорируются вектором $$\tau$$. Ясно, что коэффициенты $$\mu_\tau$$ для матриц $$K$$ и $$E$$ совпадают). Затем вычисляем значения $$\mu_\tau(K\setminus\mbk,m)$$ и $$\mu_{\tau'}(K\setminus\mbk,J)$$, снова применяя (13.6) и т. д., пока не получим "пустые" матрицы (т. е. матрицы с нулевым числом строк).
А11. АЛГОРИТМ $$(E, n,m, T, \mu)$$.
$$\begin{equation*}\\ \text{Дано: \qquad $m \in \mathbb N$,$n \in \mathbb N$;$E$-$n\!\times\! m$-матрица}\\ \text{Надо: \qquad $T$-множество допустимых векторов матрицы $E$;}\\ \text{ \qquad \qquad $\mu$- вектор типа $\mathbb Z$ с индексами из $T$.}\\ \text{Переменные: $J$ - множество типа $1..m$;}\\ \text{\qquad \qquad $K$- множество типа \{вектор типа $\mathbb N$ с индексами $1..m$\}.}\\ \text{Начало} \\ \text{сформировать множество $T$ допустимых векторов}\\ \text{цикл для каждого $\tau\in T$}\\ \text{\qquad \qquad $\mu_\tau:= 0$}\\ \text{\qquad \qquad $J:= \{ 1,\dots,m\}$}\\ \text{\qquad \qquad $K:= \{ \textbf{e}_i \mid \textbf{e}_i\leq \tau \} \text { где } \textbf{e}_i$ - строка матрицы $E$}\\ \text{ \qquad \qquad $v_\tau := 1$}\\ \text{\qquad \qquad NEXTINDEX $(J, K, v_\tau, \mu_\tau)$}\\ \text{конец цикла}\\ \text{Конец}\\ \text{Алгоритм NEXTINDEX $(J, K, v_\tau, \mu_\tau)$}\\ \text{Дано: $J$- множество типа $1..m$}\\ \text{\qquad $K$- множество типа \{вектор типа $\mathbb N$ с индексами $1..m$\}.}\\ \text{\qquad $v_\tau$ - элемент типа $\pm 1$}\\ \text{Надо:}\\ \text{$\mu_\tau$ - вектор типа $ \mathbb N$ с индексами из $T$.}\\ \text{Глобальные переменные: $m \in \mathbb N;$}\\ \text{\qquad $\tau$ - вектор типа $\mathbb N$ с индексами $1..m$.}\\ \text{Начало}\\ \text{цикл для каждой строки $\textbf{k}=\{k_1,\dots,k_m\}$ матрицы $K$, такой,}\\ \text{\qquad что $k_{i_1}=\tau_{i_1}$,}\\ \text{\qquad где $i_1$- первый элемент множества $J$}\\ \text{\qquad $K := K \setminus \textbf{k}$}\\ \text{\qquad $v_\tau := - v_\tau$}\\ \text{\qquad $J' := \{ j \in J \mid k_j=\tau_j\}$}\\ \text{\qquad $J=J\setminus J'$}\\ \text{\qquad выбор}\\ \text{\qquad \qquad $K=\emptyset \ J=\emptyset \implies \mu_\tau:= \mu_\tau+v_\tau$}\\ \text{\qquad \qquad $K\neq\emptyset \ J\neq\emptyset \implies \text{\tt NEXTINDEX}(J,K, v_\tau, \mu_\tau)$}\\ \text{\qquad конец выбора}\\ \text{\qquad $J := J \cup J'$}\\ \text{конец цикла}\\ \text{Конец} \end{equation*}$$Чтобы оценить асимптотическую сложность алгоритма A11 для достаточно больших $$n \in \mathbb N$$,
заметим, прежде всего, что при фиксированном векторе $$\tau =
(\tau_1,\dots,\tau_m) \in T$$ построение $$K=K(\tau )$$ требует не
более $$mn$$ сравнений чисел (на этом шаге мы запоминаем все
пары $$(k,j) \in \mathbb N_n \times \mathbb N_m$$, для которых $$e_{kj}=
\tau_j$$ ). Далее, выполнение элементарных операций
для всех вызовов алгоритма NEXTINDEX (для
фиксированного $$\tau$$ ) требует не более $$h_1h_2\dots
h_m$$ сравнений, где $$h_\nu=h_\nu(\tau)$$ $$(1\leq\nu\leq
m)$$ обозначает число
строк $$\textbf{k}=(k_1,\dots,k_m)$$ матрицы $$K(\tau)$$, таких,
что $$k_\nu=\tau_\nu$$ для всех $$\nu=1,\dots,m$$. Легко
видеть, что общее число операций для всех вызовов
алгоритма NEXTINDEX (с точностью до постоянного множителя это число
равно $$\sum\limits_{\tau\in T}h_1(\tau)\dots h_m(\tau )$$ ) не
превосходит $$$Card \{(a_1,\dots,a_m) \in \mathbb N^m \mid \text{ для каждого } \nu \in \mathbb N_m$$$ для каждого $$\nu \in
\mathbb N_m$$ существует $$i=i(\nu
)\in\mathbb N_n$$, такое, что $$a_\nu= e_{i\nu}\} $$, и это не
превосходит $$n^m$$.
Поэтому для достаточно больших $$n\in\mathbb N$$ асимптотическая сложность
алгоритма A11 имеет
порядок $$n^{m+1}$$.
Другой способ вычисления размерностного
многочлена $$\omega_E(t)$$ для $$n\!\times\!
m$$ -матрицы $$E$$ состоит в следующем. Для $$n<m$$ можно
вычислять
многочлен $$\omega_E(t)$$, пользуясь алгоритмом A9. Пусть $$n\geq m$$. В
этом случае применяем к $$E$$ соотношение (12.3), в
котором $$\textbf{e}$$ -
строка с максимальным значением элемента в первом столбце
матрицы $$E$$.
(Тривиальные случаи: если $$E=(0)$$, то $$\omega_E=0$$ ;
если $$n=1$$, применяем
алгоритм (12.3).) Легко видеть, что
число нулевых столбцов в матрице $$H$$ (см. (12.3)) больше, чем
в матрице $$E$$, и число строк в каждой из
матриц $$E\setminus\textbf{e}$$, $$K$$ меньше чем в $$E$$.
Затем применяем описанную процедуру к
матрице $$E\setminus\textbf{e}$$ и т.д., пока не получим матрицу,
размерностный
многочлен которой можно вычислить по алгоритму A9. В результате этого
процесса мы получаем представление требуемого
многочлена $$\omega_E(t)$$ в виде
линейной комбинации
многочленов $$\omega_{\textbf{e}},\omega_{H_1},\dots,\omega_{H_{n-1}}$$ (со
сдвинутыми аргументами),
таких, что каждая матрица $$H_i$$ имеет ровно $$i$$ строк и
число ее нулевых
столбцов на один больше, чем в $$E$$.
Многочлен $$\omega_{\textbf{e}}$$ и некоторые из
многочленов $$\omega_{H_i}$$ вычисляются по алгоритму A9 (в тех
случаях, когда этот алгоритм нужно применять в соответствии с вышеприведенными
рассуждениями). Для вычисления остальных
многочленов $$\omega_{H_i}$$ снова
применяем соотношение (12.3) и продолжаем в том же духе. Заметим, что
если первый столбец в матрице $$E$$ нулевой и $$m > 1$$, то
число операций в
вычислении $$\omega_E$$ по предлагаемой схеме совпадает с числом
операций при
вычислении размерностного многочлена $$n\!\times\! (m-1)$$ -матрицы.
Кроме того,
если $$E$$ - $$n\!\times\!1$$ -матрица, то все ее строки
кроме той, которая
содержит элемент $$\min_{1\leq i\leq n}\{ e_{i1}\}$$, являются
лишними, так что
вычисление размерностного многочлена по формуле $$\omega_E=\min_{1\leq
i\leq
n}\{ e_{i1}\}$$ требует $$(n-1)$$ операцию. Таким образом,
если $$f(n,m)$$ обозначает число элементарных операций (сложение,
сравнение или умножение)
необходимых для вычисления размерностного
многочлена $$\omega_E(t)$$ матрицы $$E$$ размера $$n\!\times\! m$$, то $$f(n,m)\leq(n-1)+f(n-1,m)+f(n-1,m-1)$$. Поскольку $$f(n,1)=n-1$$, имеем$$\begin{align*}
f(n,2)\leq 2(n-1) + f(n-1,2)\\
amp; \leq 2((n-1) + (n-2)) + f(n-2,2) \leq \dots\\
\leq 2((n-1) + (n-2) +\dots+1)= \frac {n(n-1)}2\cdot 2\leq
n^2;\\
f(n,3)\leq n^2+(n-1)^2+\dots+1 \leq n^3;\\
\vdots\\
f(n,k)\leq n^{k-1}+ (n-1)^{k-1}+\dots+1\leq n^k
\end{align*}$$
и т. д. Поэтому алгоритм вычисления размерностного многочлена, основанный на
приведенной схеме (см. алгоритм A12 ), имеет асимптотическую сложность $$O(n^m)$$.
А12. АЛГОРИТМ $$(E, n,m, \omega)$$.
$$\begin{equation}\\ \text{Дано: \quad $n\in\mathbb N; m\in\mathbb N$;$n\!\times\!m$-матрица$E$.} \\ \text{Надо: \qquad$\omega(t)=\omega_E(t)$- многочлен Гильберта матрицы $E$.}\\ \text{Пер.: \qquad $h \in \mathbb N$}\\ \text{\qquad $J$- множество элементов типа $1..m$;}\\ \text{\qquad $\textbf{e}$- вектор типа $\mathbb N$ с индексами $1..m$;}\\ \text{\qquad $F$- матрица типа $\mathbb N$, число столбцов которой не более $m$,}\\ \text{ \qquad а число строк - не более $n$.}\\ \text{Начало}\\ \text{$h:=n$}\\ \text{$F:= E$}\\ \text{если $h \leq m $ то }\\ \text{\qquad Алгоритм A9 $(E,n,m,\omega)$}\\ \text{иначе}\\ \text{\qquad $J:=\{$ ненулевые столбцы $F\}$}\\ \text{\qquad если $J=\emptyset $ то $\omega(t) := 0$}\\ \text{\qquad иначе если $Card J = 1$ то}\\ \text{\qquad\qquad $c:=$ минимальный элемент столбца $j \in J$}\\ \text{\qquad\qquad $\omega := \binom {t+m}m-\binom {t+m-c}m$}\\ \text{\qquad иначе}\\ \text{\qquad\qquad $j:=\{$ первый элемент множества $J\}$}\\ \text{\qquad \qquad $\textbf{e}:=\{$ первая строка матрицы $F$ с минимальным}\\ \text{\qquad\qquad\quad элементом в $j$ -м столбце $\}$}\\ \text{\qquad\qquad $F:= F\setminus\textbf{e}$}\\ \text{\qquad\qquad Алгоритм A12$(F,h-1,m,\omega)$}\\ \text{\qquad\qquad $v(t):= \omega(t)$}\\ \text{\qquad\qquad $F:= \{\textbf{f}-\textbf{e} \mid \textbf{f}$ - строка матрицы $F, \textbf{f} \neq \textbf{e}\} $}\\ \text{\qquad\qquad Алгоритм A12 $(F,h-1,m,\omega)$}\\ \text{\qquad\qquad $\omega(t) := v(t) - \omega (t-|\textbf{e}|)$}\\ \text{\qquad конец если} \\ \text{конец если}\\ \text{Конец} \end{equation}$$Символ $$\dotminus$$, которым мы пользуемся в алгоритме A12, обозначает следующую операцию на векторах:$$(a_1,\dots,a_m) \dotminus(b_1,\dots,b_m) = (c_1,\dots,c_m),$$ где $$c_i=\max(a_i-b_i,0)$$ для всех $$i=1,\dots,m$$. При этом, если $$m > 2$$, то $$e_i$$ $$(1\leq i\leq m)$$ обозначает $$i$$ -ю координату элемента $$\textbf{e} \in \mathbb N^m$$.
В заключение этого параграфа рассмотрим алгоритм вычисления размерностного
многочлена, асимптотическая сложность которого
меньше асимптотической сложности алгоритмов A9, A10, A11 и A12. Кроме того,
представим алгоритм вычисления
Пусть $$\mathbb Q[t]$$ - кольцо многочленов над полем рациональных чисел. Для каждого $$s\in\mathbb N$$ пусть $$\Delta_s$$ и $$\Delta^{-1}$$ обозначают операторы, действующие на $$\mathbb Q[t]$$ следующим образом:$$\begin{equation}\ \Delta_s(f(t))=f(t)-f(t-s) \end{equation}$$ и если $$f(t) =\sum_{i\in\mathbb N} a_i\binom{t+i}i$$ $$(a_i\in\mathbb Q)$$ для всех $$i\in\mathbb N$$, то$$\begin{equation}\label{13.7apos;} \Delta^{-1}f(t)=\sum_{i\in\mathbb N} a_i\binom {t+1+i}{i+1}. \qquad \qquad \qquad \ecno(13.7') \end{equation}$$
Отметим, что операторы $$\Delta_s$$ и $$\Delta^{-1}$$ $$(s \in \mathbb N)$$, удовлетворяют следующему тождеству:$$\begin{equation} \Delta_s\Delta^{-1}f(t) =f(t)+f(t-1)+ \dots+f(t-s+1). \end{equation}$$ В частности,$$\Delta_1\Delta^{-1}= \id_{\mathbb Q[t]}.$$ Действительно, пусть$$f(t) =\sum\limits_{i\in\mathbb N} a_i\binom {t+i}i$$ $$a_i\in\mathbb Q$$ для всех $$i\in\mathbb N$$, и $$a_i=0$$ для почти всех $$i\in\mathbb N$$ и пусть $$s \in \mathbb N$$. По (11.4) имеем$$\begin{multiline*} \Delta_s\Delta^{-1}f(t) =\sum\limits_{i\in\mathbb N} a_i\left[\binom{t+i+1}{i+1}-\binom {t+i+1-s}{i+1}\right] =\sum\limits_{i\in\mathbb N} a_i\sum\limits_{r=0}^{s-1} \binom {t+i+1-s+r}i =\sum\limits_{i\in\mathbb N} a_i\sum\limits_{r=0}^{s-1} \binom {t+i-r}i\\ =\sum\limits_{r=0}^{s-1} \sum\limits_{i\in\mathbb N} a_i\binom {t+i-r}i =\sum\limits_{r=0}^{s-1} f(t-r). \end{multliine*}$$
13.10. ЛЕММА. Пусть $$E=(e_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$$ - $$n\!\times\!m$$ - матрица над $$\mathbb N$$, $$k\in\mathbb N_m$$ и $$a=\min_{i=1}^n\{e_{ik} \mid e_{ik}\neq 0\}$$. Через $$E_1$$ обозначим матрицу, полученную из $$E$$ удалением $$k$$ -го столбца и всех строк с ненулевым элементом в $$k$$ -м столбце. Далее, пусть $$H =(h_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$$ - $$n\!\times\! m$$ -матрица с элементами$$\[ h_{ij}=\begin{cases} \max(e_{ik}- a,0), \text { если }j=k\\ e_{ij}, \text { если } j\neq k\end{cases}\quad (1\leq i\leq n,\ 1\leq j\leq m).$$ Тогда$$\begin{equation} \omega_E(t)=\Delta_a\Delta^{-1}\omega_{E_1}(t)+\omega_H(t-a), \end{equation}$$ где $$\omega_E(t)$$, $$\omega_H(t)$$ и $$\omega_{E_1}(t)$$ - размерностные многочлены матриц $$E$$, $$H$$ и $$E_1$$ соответственно.
В частности, если$$E= \begin{pmatrix} k 0\dots0\\ \begin{matrix} 0\\ \vdots \\ 0\end{matrix} E_1\end{pmatrix},$$ где $$e_{11}=k$$, а все остальные элементы первого столбца и первой строки равны нулю, то $$\omega_E(t)=\Delta_k\cdot\Delta^{-1}\omega_{E_1}(t)$$.
ДОКАЗАТЕЛЬСТВО. Применяя формулу (12.2) к матрице $$E$$ и вектору $$(0,\dots,0,a,0,\dots,0)$$ ( $$a$$ - $$k$$ -я координата этого вектора), получаем$$\omega_E(t) = \omega_{E\cup (0,\dots,0,a,0,\dots,0)}(t) + \omega_H(t-a).$$ Теперь применим (12.2) к матрице $$E\cup (0,\dots,0,a,0,\dots,0)$$ и вектору $$(0,\dots,0,1,0,\dots,0)$$ (где 1 стоит на $$k$$ -м месте). По теореме 12.8(8) получим$$\omega_{E\cup (0,\dots,0,a,0,\dots,0)}(t)= \omega_{E_1}(t)+ \omega_{E\cup (0,\dots,0,a-1,0,\dots,0)}(t-1).$$ Повторяя эту операцию $$a$$ раз, получим равенство$$\omega_{E\cup (0,\dots,0,a,0,\dots,0)}(t) =\omega_{E_1} (t) + \omega_{E_1}(t-1)+\dots+ \omega_{E_1}(t-(a-1)),$$ откуда следует (13.9) (см. (13.8)).
Теперь можно предложить следующую схему вычисления размерностного многочлена $$\omega_E(t)$$ матрицы $$E=(e_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$$, основанную на формуле (13.9). Сначала, выбрав вектор $$(a,0,\dots,0) \in \mathbb N^m$$, где $$a=\min_{1\leq i\leq n} \{ e_{i1}\ \mid e_{i1}\neq 0\}$$, и применив лемму 13.10, сведем нашу задачу к вычислению размерностного многочлена матрицы $$E_1$$ с $$(m-1)$$ столбцом и размерностного многочлена матрицы $$H = (h_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$$, такой, что $$0\leq h_{i1}< e_{i1}$$ $$(1\leq i\leq n)$$. Для определения $$\omega_H(t)$$ применим формулу (13.9) (с матрицей $$H$$ вместо $$E$$ ) и продолжим процесс до тех пор, пока не получим представление $$\omega_E(t)$$ в виде суммы размерностных многочленов матриц с $$(m-1)$$ столбцом и размерностного многочлена $$\omega_{H_1}(t)$$, где $$H_1$$ - $$n\!\times\! m$$ -матрица с нулевым первым столбцом. Для вычисления $$\omega_{H_1}(t)$$ применяем описанную процедуру ко второму столбцу и т. д.
13.11. ПРИМЕР. Вычислим многочлен Гильберта $$\omega_E(t)$$ матрицы$$E=\begin{pmatrix} 200\\020\end{pmatrix}.$$
Сначала находим $$a=2$$. Применяя (13.9), получаем$$\omega_E(t)=\Delta_2\Delta^{-1}\omega_{E_1}(t)+\omega_H(t-2),$$ где $$E_1 =(2,0)$$ и $$H=\begin{pmatrix} 000\\020\end{pmatrix}$$. Ясно, что $$\omega_H(t)=0$$ (см. теорему 12.8(6)) и $$\omega_{E_1}(t)=\binom {t+2}2 - \binom {t+2-2}2$$, следовательно, (см. 13.8)$$\begin{align*} \omega_E(t){} = \Delta_2\Delta^{-1}\omega_{E_1}(t) = \omega_{E_1}(t) + \omega_{E_1}(t-1) \\ {}= \binom {t+2}2 - \binom t2 + \binom {t+1}2-\binom {t-1}2 = 4t. \end{align*}$$
Заметим, что вычисление многочлена Гильберта $$\omega_E(t)$$ по одному из алгоритмов A9, A10, A11 или A12 приводит к представлению этого многочлена в виде $$\omega_E(t) = \binom {t+3}3-2\binom {t+3-2}3 + \binom {t+3-4}3$$. Однако, применяя лемму 13.10, мы получаем многочлен $$\omega_E(t)$$ в виде суммы многочленов вида $$a_k\binom {t+i}k$$ $$(i \in\mathbb Z$$, $$k \in \mathbb N$$, $$a_k\in\mathbb Z)$$. Максимальная степень этих многочленов меньше степени многочленов, фигурирующих в подобном представлении для $$\omega_E(t)$$, когда $$\omega_E(t)$$ вычисляется по одному из алгоритмов A9, A10, A11 или A12.
Следующая лемма дает возможность оценивать степень многочлена Гильберта и
вычислять его
13.12. ЛЕММА. Пусть $$E = (e_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$$ - $$n\!\times\! m$$ -матрица над $$\mathbb N$$ и $$\tau\le m$$ - неотрицательное целое число. Тогда $$\deg\omega_E(t)<\tau$$ если и только если для любого подмножества $$I$$, состоящего из $$m-\tau$$ элементов множества $$\{1,\dots,m\}$$, существует строка $$e_I$$ матрицы $$E$$ , такая, что все элементы этой строки, стоящие в столбцах с индексами из $$I$$ , равны нулю. В частности, $$\omega_E(t)=\const$$ тогда и только тогда, когда $$E$$ содержит диагональную подматрицу.
Доказательство леммы проводится индукцией по сумме элементов матрицы $$E$$ и оставляется читателю в качестве упражнения.
Матрицу $$E$$ над $$\mathbb N$$ назовем нормализованной, если каждый столбец матрицы $$E$$ содержит нуль. Ниже будет показано, что если $$E$$ - нормализованная $$n\!\times\!m$$ -матрица, то алгоритм вычисления размерностного многочлена $$\omega_E(t)$$, основанный на лемме 13.10, требует меньшего числа операций, чем для произвольной $$n\!\times\! m$$ -матрицы. В то же время, для сведения задачи вычисления размерностного многочлена произвольной $$n\!\times\! m$$ -матрицы над $$\mathbb N$$ к аналогичной задаче для нормализованной $$n\!\times\! m$$ -матрицы можно воспользоваться теоремой 12.8(9).
13.13. ЛЕММА. Пусть $$E = (e_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$$ - $$n\!\times\! m$$ -матрица над $$\mathbb N$$ и предположим, что $$\deg \omega_E=0$$.
ДОКАЗАТЕЛЬСТВО. (1) Если $$e_{11}=0$$, то в $$E$$ имеется нулевая строка, следовательно, $$\omega_E=0$$ (см. теорему 12.8(6)). Если $$e_{11}>0$$, то применяя (12.2) к $$E$$ и $$\textbf{e}=(1,0,\dots,0)\in\mathbb N^m$$, получаем$$\omega_E = \omega_{E\cup\textbf{e}}+\omega_H = \omega_{E_1}+ \omega_H, \text{ где } H =\begin{pmatrix} e_{11}-1 0\dots0\\ \begin{matrix} 0\ \vdots \\ 0\end{matrix} E_1\end{pmatrix}.$$ Таким образом, индукция по $$e_{11}$$ дает требуемый результат.
(2) Лемма 13.12 утверждает, что $$E$$ содержит строку, в которой ненулевой может быть только первая координата. Значит $$H$$ содержит нулевую строку, следовательно, $$\omega_H=0$$.
(3) Соотношение (13.10) следует из (12.2), записанного для $$E$$ и $$(a,0,\dots,0)\in\mathbb N^m$$.
Пользуясь леммой 13.13, можно предложить следующий метод вычисления многочлена Гильберта $$\omega_E$$ матрицы $$E$$ в случае, когда $$\deg\omega_E=0$$: применить соотношение (13.10) к $$\omega_E$$ (где $$a$$ - минимальный ненулевой элемент в первом столбце матрицы $$E$$ ), затем выписать аналогичное представление для $$E_2$$ и т. д. После конечного числа таких шагов получим представление многочлена $$\omega_E$$ в виде суммы многочленов Гильберта матриц $$F_1,\dots,F_r$$ $$(r\in\mathbb N$$, $$r\geq 1)$$ с $$(m-1)$$ столбцами и многочлена Гильберта $$\omega_H$$, где элементы матрицы $$H=(h_{ij})_{\substack{1\leq i\leq n\\1\leq j\leq m}}$$ равны$$h_{ij}=\begin{cases} e_{ij}, \text{если } 1\leq i\leq n,\ 2\leq j\leq m\\ 0, \text{если } 1\leq i\leq n,\ j=1,\end{cases}$$ так что $$\omega_H=0$$ (см. лемму 13.13(2)). Применяя описанную процедуру к каждой из матриц $$F_1,\dots,F_r$$, мы сводим вычисление многочлена $$\omega_E$$ к вычислению многочленов Гильберта для некоторых матриц с $$(m-2)$$ столбцами и т.д., пока не получим матрицы, состоящие из единственного столбца. Как мы знаем, многочлен Гильберта такой матрицы совпадает с ее минимальным элементом.
В общем случае (без условия $$\deg \omega_E=0$$ ) вычисление размерностного многочлена $$\omega_E(t)$$ для $$n\!\times\! m$$ -матрицы $$E=(e_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$$ по описанной схеме (используя (13.9) вместо (13.10)) можно свести к вычислению размерностных многочленов матриц, число столбцов в которых меньше $$m$$, и размерностных многочленов некоторых $$n\!\times\! m$$ -матриц с нулевым первым столбцом. Более точно: если первый столбец матрицы $$E$$ содержит ненулевые элементы, то мы полагаем $$a=\min_{1\leq i\leq n} \{ e_{i1} | e_{i1}\neq0 \} $$ и применяем (13.19). Затем применяем то же самое соотношение к $$H$$ (см. лемму 13.10) и т. д. В результате получим разложение многочлена $$\omega_E(t)$$ в сумму многочленов вида $$\omega_{E_i}(t-a_i)$$, где $$a_i\in \mathbb N$$ и $$E_i$$ - либо матрица, число столбцов в которой меньше $$m$$, либо $$n\!\times\! m$$ -матрица с нулевым первым столбцом. Для вычисления размерностных многочленов матриц второго типа применяем описанный метод ко второму столбцу и т. д., пока не получим представление многочлена $$\omega_E(t)$$ в виде суммы размерностных многочленов матриц, число столбцов в которых меньше $$m$$, и размерностных многочленов матриц с не более чем двумя ненулевыми столбцами. Размерностный многочлен матрицы последнего типа может быть найден с помощью следующего утверждения.
13.14. ЛЕММА. Пусть$$E=\begin{pmatrix} e_{11} e_{12} 0 \hdots 0 \\ e_{21} e_{22} 0 \hdots 0 \\ \vdots \vdots \vdots \ddots \vdots \\ e_{n1} e_{n2} 0 \hdots 0 \end{pmatrix}$$ - нормализованная $$n\!\times\! m$$ -матрица над $$\mathbb N\ (m\geq 2)$$ . Предположим, что $$0 = e_{11}< e_{21}<\dots< e_{n1}$$ и $$e_{12}> e_{22}>\dots> e_{n2}= 0$$. Тогда$$\begin{equation} \omega_E(t)=\sum_{i=1}^{n-1}\Delta_{(e_{i+1,1}-e_{i1})} \Delta^{-1}\omega_{\textbf{e}_i}(t-e_{i1}), \end{equation}$$ где $$\textbf{e}_i= (e_{i2},0,\dots,0) \in \mathbb N^{m-1}\ (i=1,\dots,n-1)$$.
ДОКАЗАТЕЛЬСТВО. Воспользуемся индукцией по $$n$$. Случай $$n=1$$ тривиален. Пусть $$n>1$$, и предположим, что утверждение леммы доказано для всех матриц, число строк которых меньше $$n$$. Для доказательства соотношения (13.11) для $$n\!\times\! m$$ -матрицы $$E = (e_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$$, у которой $$e_{ij}=0$$ $$(1\leq i\leq n$$, $$3\leq j\leq m)$$, прежде всего заметим, что если $$a=\min_{1\leq i\leq n} \left( e_{i1} \mid e_{i1}\neq0\right) =e_{21}$$, то$$\omega_E(t) = \Delta_a\Delta^{-1} \omega_{E_1}(t)+\omega_H(t-a),$$ где $$E_1 = (e_{12},0,\dots,0) \in \mathbb N^{m-1}$$ и$$H=\begin{pmatrix} 0 e_{12} 0 \hdots 0 \\ 0 e_{22} 0 \hdots 0 \\ e_{31}-e_{21} e_{32} 0 \hdots 0 \\ \vdots \vdots \vdots \ddots \vdots \\ e_{n1}-e_{21} e_{n2} 0 \hdots 0 \end{pmatrix}$$ (см. лемму 13.10). Первая строка матрицы $$H$$ является лишней, следовательно, $$\omega_H=\omega_{H_1$$, где$$H_1=\begin{pmatrix} 0 e_{22} 0 \hdots 0 \\ e_{31}-e_{21} e_{32} 0 \hdots 0 \\ \vdots \vdots \vdots \ddots \vdots \\ e_{n1}-e_{21} e_{n2} 0 \hdots 0 \end{pmatrix}.$$ По предположению индукции имеем$$\omega_H(t) = \omega_{H_1}=\sum_{i=2}^{n-1} \Delta_{(e_{i+1,1}-e_{i1})} \Delta^{-1} \omega_{ \textbf{e}_i}(t-e_{i1}),$$ следовательно,$$\begin{align*} \omega_E(t) = \Delta_{e_{21}} \Delta^{-1}\omega_{E_1}(t) +\sum_{i=2}^{n-1}\Delta_{(e_{i+1,1}-e_{i1})}\Delta^{-1}\omega_{\textbf{e}_i}(t-e_{i1})\ =\smash{\sum_{i=1}^{n-1}}\Delta_{(e_{i+1,1}-e_{i1})}\Delta^{-1}\omega_{\textbf{e}_i}(t-e_{i1}). \tag*\qedsymbol \end{align*}$$
13.15. СЛЕДСТВИЕ. Пусть$$E=\begin{pmatrix} e_{11} e_{12} \\ e_{21} e_{22} \\ \vdots \vdots \\ e_{n1} e_{n2} \end{pmatrix}$$ - $$n\!\times\! 2$$ -матрица над $$\mathbb N$$, такая, что $$0 = e_{11}< e_{21}< \dots < e_{n1}$$, $$e_{12}> e_{22}>\dots> e_{n2}= 0$$. Тогда $$\begin{equation} \omega_E(t)=\sum_{i=1}^{n-1}(e_{i+1,1}-e_{i1}) e_{i2}. \ \end{equation}$$
А13. АЛГОРИТМ $$(E, n,m, \omega)$$.
$$\begin{equation}\\ \text{Дано: \quad $n\in\mathbb N;\ m\in\mathbb N$; $n\!\times\!m$-матрица $E$. }\\ \text{Надо:\qquad $\omega_E(t)$- многочлен Гильберта матрицы $E$.}\\ \text{Переменные: $P_0, P_1$- многочлены;}\\ \text{\qquad $N_S$- текущее значение первой координаты;}\\ \text{\qquad $N_R$- следующее значение первой координаты;}\\ \text{\qquad $E_0$- последовательность $(m-1)$-мерных векторов.}\\ \text{Начало}\\ \text{$\omega(t):=0$}\\ \text{если $n=0$ тоесли $n=0$ то $\omega(t):=\binom {t+m}m$}\\ \text{иначе $\textbf{v}:=(v_1,\dots,v_m)$, \ где $v_j =\min_{1\leq i\leq n} \{e_{ij}\}\ (j=1,\dots,m)$}\\ \text{ \qquad $E := (e_{ij}-v_j)_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$}\\ \text{\qquad $K :=$ \{индексы ненулевых столбцов матрицы $E$\}}\\ \text{\qquad выбор}\\ \text{\qquad $Card K=2$, $K=\{ j,p\} \implies$ сортировать строки по возрастанию $j$-го столбца}\\ \text{\qquad \qquad удалить лишние строки }\\ \text{$\omega:=\omega(t)+\sum\limits_{i=1}^{n-1}\Delta_{(e_{i+1,j}-e_{ij})}\Delta^{-1}\omega_{\textbf{e}_i}(t-e_{ij})$,}\\ \text{\qquad \qquad \qquad где $\textbf{e}_i=(e_{ip},0,\dots,0)\in\mathbb N^{m-1}$}\\ \text{\qquad $Card K>2 \Rightarrow$ взять $k \in K$}\\ \text{\qquad \qquad переставить $k$-й столбец с первым}\\ \text{\qquad \qquad $N_S := 0$}\\ \text{\qquad \qquad $E_0 := \emptyset$}\\ \text{\qquad \qquad цикл для каждого ненулевого $e_{i1}$ в возрастающем порядке}\\ \text{\qquad \qquad \qquad $N_R := e_{i1}$}\\ \text{\qquad \qquad \qquad $E_0$: добавить последовательность строк}\\ \text{\qquad \qquad \qquad \qquad $\{ (e_{j2},\dots,e_{jm})|e_{j1}= N_S\}$}\\ \text{\qquad \qquad \qquad $N_0 :=$ число векторов в $E_0$}\\ \text{\qquad \qquad \qquad Алгоритм A13 $(E_0,N_0,m-1,P_0(t))$}\\ \text{\qquad \qquad \qquad $P_0(t):=\Delta_{(N_R-N_S)}\Delta^{-1}P_0(t)$}\\ \text{\qquad \qquad \qquad $\omega(t):=\omega(t)+P_0(t-N_S)$}\\ \text{\qquad \qquad \qquad $N_S:=N_R$}\\ \text{\qquad \qquad конец цикла}\\ \text{\qquad \qquad $E$: обнулить первый столбец}\\ \text{\qquad \qquad Алгоритм A13 $(E,n,m,P_1(t))$}\\ \text{\qquad \qquad $\omega(t):=\omega(t)+P_1(t-N_S)$}\\ \text{\qquad конец выбора}\\ \text{\qquad $\omega(t):=\omega(t-|\textbf{v}|)+\binom{t+m}m-\binom{t+m-|\textbf{v}|}m$}\\ \text{конец если}\\ Конец \end{equation}$$Приведенный здесь алгоритм A13 вычисления многочлена Гильберта $$\omega_E(t)$$ для $$n\!\times\!m$$ -матрицы $$E$$ основан на данной выше схеме. В соответствии с ней, воспользуемся (13.8), чтобы представить многочлен $$\omega_E(t)$$ в виде суммы многочленов Гильберта матриц, которые содержат менее $$m$$ столбцов, и многочлена Гильберта $$n\!\times\!m$$ -матрицы $$E'$$, содержащей не более двух ненулевых столбцов (без потери общности можно считать, что ненулевыми являются два первых столбца матрицы $$E'$$ ). Многочлен $$\omega_{E'}(t)$$ вычисляется с помощью соотношения (13.10). Сначала переупорядочим строки так, чтобы элементы первого столбца удовлетворяли условию леммы 13.14 (такое переупорядочение требует $$\sim n\log n$$ элементарных операций). Тогда видно, что если второй ненулевой столбец не упорядочен в обратном порядке, то матрица $$E'$$ содержит лишние строки (в точности те строки $$\textbf{e}_i \ (1\leq i\leq n)$$, в которых $$e_{12}\geq e_{j2}$$ для некоторого $$j \in \mathbb N,\ 1\leq j<i$$ ). Таким образом, получаем следующую оценку числа $$f(n,m)$$ элементарных операций, которые требуются для вычисления многочлена Гильберта $$\omega_E(t)$$ для $$n\!\times\! m$$ -матрицы $$E$$ с помощью алгоритма A13:$$\begin{align*} f(n,m)\leq n\log n+f(n,m-1)+\sum_{i=1}^kf(b_i,m-1)\\ \leq n\log n+nf(n,m-1) \end{align*}$$ где $$1\leq k<n;\ b_1,\dots,b_k \in \N$$ ; $$1\leq b_i\leq n$$ $$(i=1,\dots,k)$$. Следовательно, алгоритм A13 имеет асимптотическую сложность $$\sim n^{m-1 \log n$$ при $$m\geq 2$$ (если $$m=1$$, то асимптотическая сложность $$\sim n$$ ).
13.16. ПРИМЕР. Вычислим многочлен Гильберта матрицы$$E=\left( \smallmatrix 1 0 0 1 \\ r-2 0 1 0 \\ r-3 0 2 0 \\[-6pt] \vdots \vdots \vdots \vdots \\ i 0 r-i-1 0 \\[-6pt] \vdots \vdots \vdots \vdots \\ 1 0 r-2 0 \\ 0 1 0 r-2\endsmallmatrix\right)$$ $$(r\in \mathbb N,\ r\geq 3)$$ при помощи алгоритма A13. В процессе вычислений последовательно применяем (13.8), начиная с последнего столбца матрицы $$E$$. Прежде всего запишем$$\omega_E(t) = \Delta_1\Delta^{-1}\omega_{E_1}(t) + \omega_H(t-1) = \omega_{E_1}(t) + \omega_H(t-1),$$ где$$E_1=\left( \smallmatrix r-2 0 1 \\ r-3 0 2 \\[-6pt] \vdots \vdots \vdots \\ 1 0 r-2\endsmallmatrix\right),H=\left( \smallmatrix 1 0 0 0 \\ r-2 0 1 0 \\ r-3 0 2 0 \\[-6pt] \vdots \vdots \vdots \vdots \\ i 0 r-i-1 0 \\ \vdots \vdots \vdots \vdots \\ 1 0 r-2 0 \\ 0 1 0 r-3\endsmallmatrix\right).$$ По теореме 12.8(8) имеем$$\begin{align*} \omega_H(t-1)= \omega_{(1,0,r-3)}(t-1) =\binom{t-1+3}3-\binom{t-1+3-(r-2)}3\\ = \binom {t+2}3 - \binom {t+4-r}3. \end{align*}$$ Применяя (12.2) к $$E_1$$ и $$(1,0,1)$$, получаем $$\omega_{E_1}(t)=\omega_{(1,0,1)}(t)+ \omega_{H_1}(t-2)$$, где$$H_1=\left( \smallmatrix r-3 0 0 \\ r-4 0 1 \\[-6pt] \vdots \vdots \vdots \\ 1 0 r-4 \\ 0 0 r-3\endsmallmatrix\right),$$ так что из формулы (13.10) следует, что$$\begin{align*} \omega_{H_1}(t-2) = \sum_{i=1}^{r-3}\Delta_1\Delta^{-1}\omega_{(r-2-i,0)}(t-2-(i-1))\\ =\sum_{i=1}^{r-3}\omega_{(r-2-i,0)}(t-i-1)\\ =\sum_{i=1}^{r-3}\left[\binom {t-i-1+2}2 -\binom {t-i-1+2-(r-2-i)}2\right]\\ =\sum_{i=1}^{r-3}\left[\binom {t-i+1}2 -\binom {t+3-r}2\right]\\ = \frac{(r-3)(r-2)}2 t - \frac{(r-2)(r-3)(2r-5)}6. \end{align*}$$ Поэтому,$$\begin{align*} \omega_{E_1}(t)={}\binom{t+3}3-\binom{t+3-2}3+\frac{(r-3)(r-2)}2t -\frac{(r-2)(r-3)(2r-5)}6 \\ ={}(t+1)^2 + \frac{(r-3)(r-2)}2 t -\frac{(r-2)(r-3)(2r-5)}6, \end{align*}}$$ следовательно,$$\begin{align*} \omega_E(t)={}\binom {t+2}3 - \binom {t+4-r}3 + (t+1)^2\\ +\frac{(r-3)(r-2)}2 t-\frac{(r-2)(r-3)(2r-5)}6 \\ ={}\frac r2t^2+\frac{r+2}2t-\frac{r^3-6r^2+11r-12}6. \end{align*}$$
Рассмотрим задачу вычисления
$$E = (e_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$$ — $$n\!\times\! m$$ -матрица над $$\mathbb N$$ и$$\begin{equation} \omega_E(t) =\sum_{i=0}^m a_i(E)\binom {t+i}i \end{equation}$$ ее многочлен Гильберта. Тогда по теореме 12.8(7) имеем$$a_m(E)=\begin{cases} 1,\text {если матрица $E$ пустая } (n=0)\\ 0,\text {в противном случае.}\end{cases}$$ Из теоремы 12.8(9) и леммы13.12 что$$a_{m-1}(E)=\begin{cases} 0,\text {если матрица $E$ пустая,}\\ \sum_{j=1}^m\min_{1\leq i\leq n} \{ e_{ij}\} ,\text {в противном случае.}\end{cases}$$ Вычисление коэффициента $$a_{m-2}(E)$$ (при $$m\geq 2$$ ) может основываться на следующем утверждении.
13.17. ЛЕММА. Пусть $$E = (e_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$$ — $$n\!\times\! m$$ -матрица над $$\mathbb N$$, такая, что $$m>1$$ и первый столбец матрицы $$E$$ нулевой. Пусть $$\omega_E(t) =\sum\limits_{i=0}^\tau a_i(E) \binom {t+i}i$$ — многочлен Гильберта матрицы $$E$$ и $$0<\deg\omega_E\leq \tau\ (\tau\in\mathbb N_m)$$. Далее, пусть $$E_1$$ — $$n\!\times\!(m-1)$$ -матрица, полученная из $$E$$ удалением первого (нулевого) столбца. Тогда $$\deg \omega_{E_1}\leq \tau-1$$ и $$a_\tau(E)=a_{\tau-1}(E_1)$$.
ДОКАЗАТЕЛЬСТВО. Применяя (12.2) к $$E$$ и $$(1,0,\dots,0) \in \mathbb N^m$$, получим, что $$\omega_E(t)=\omega_{E_1}(t)+\omega_E(t-1)$$. Значит, если$$$\omega_E(t) =\sum_{i=0}^\tau a_i(E) \binom {t+i}i,$ то \begin{align*} \omega_{E_1}(t)=\sum_{i=0}^\tau a_i(E_1) \binom {t+i}i =\sum_{i=0}^\tau a_i(E) \left[ \binom {t+i}i- \binom {t+i-1}i\right]\\ = \sum_{i=0}^{\tau-1} a_{i+1}(E) \binom {t+i}i, \end{align*}$$ следовательно, $$\deg \omega_{E_1}\leq\tau-1$$ и $$a_i(E_1) = a_{i+1}(E)$$ для всех $$i=0$$, $$1,\dots,\tau-1$$. В частности, $$a_\tau(E)=a_{\tau-1}(E_1)$$.
Отметим, что если для $$n\!\times\! m$$ -матрицы $$E = (e_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$$ степень многочлена Гильберта $$\omega_E(t)= \smash{\sum\limits_{i=0}^m} a_i(E) \binom {t+i}i$$ меньше или равна $$\tau$$ $$(\tau\in\mathbb N$$, $$0\leq \tau\leq m)$$, то$$\begin{equation} a_\tau(E) = a_\tau(E_1) + a_\tau(E_2), \end{equation}$$ где $$a=\min_{1\leq i\leq n}\{ e_{i1}| e_{i1}\neq0\}$$, матрица $$E_1$$ получена из $$E$$ удалением первого столбца и всех строк с нулем в первом столбце, а $$E_2= (e'_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$$ — $$n\!\times\! m$$ -матрица с элементами$$e'_{ij}=\begin{cases} e_{ij}, \text{если } j\neq 1 \\ \max\{ e_{i1}-a, 0\} ,\text{если } j=1\end{cases} \ (1\leq i\leq n,\ 1\leq j\leq m).$$ (Соотношение (13.14) легко может быть установлено применением (12.2) к $$E$$ и $$(a,0,\dots,0)\in\mathbb N^m$$.)
Прежде чем вычислять коэффициент $$a_{m-2}(E)$$ многочлена Гильберта (13.13), заметим, что, без потери общности, можно предполагать, что $$\deg\omega_E\leq m-2$$. Действительно, применяя (12.2) к $$E$$ и $$\textbf{e}=\bigl(\min\limits_{1\leq i\leq n}\{ e_{i1}\} ,\dots,\min\limits_{1\leq i\leq n}\{e_{im}\}\bigr)$$,получаем, что$$\omega_E(t) =\binom {t+m}m - \binom {t+m- |\textbf{e}|}m + \omega_{E'}(t-|\textbf{e}|),$$ где $$E' = (e'_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$$ — матрица с элементами $$e'_{ij}=e_{ij}- \min_{1\leq i\leq n}\{ e_{ij}\} $$ $$(1\leq i\leq n,\ 1\leq j\leq m)$$. Пользуясь (11.4), можно переписать последнее представление $$\omega_E(t)$$ в виде$$\begin{align*} \omega_E(t) ={}\sum_{i=0}^{|\textbf{e}|-1} \binom {t+m-1-i}{m-1} + \omega_{E'}(t-|\textbf{e}|) \\ ={} \smu{2} |\textbf{e}|\binom {t+m-1}{m-1}\!-\!\sum_{i=1}^{|\textbf{e}|-1} \left[\!\binom {t+m-1}{m-1}\!-\!\binom {t+m-1-i}{m- 1}\!\right] +\omega_{E'}(t-|\textbf{e}|) \\ ={} |\textbf{e}|\binom {t+m-1}{m-1} - \sum_{i=1}^{|\textbf{e}|-1} \sum_{k=0}^{i-1} \binom {t+m-1-i+k}{m-2} + \omega_{E'}(t-|\textbf{e}|) \\ ={}|\textbf{e}|\binom {t+m-1}{m-1} - \frac {|\textbf{e}|(|\textbf{e}|-1)}2 \binom {t+m-2}{m-2} +o(t^{m-2})+ \omega_{E'}(t-|\textbf{e}|). \end{align*}}$$
Поскольку $$\deg \omega_{E'}\leq m-2$$ (см. лемму 13.12), имеем $$a_{m-2}(E) = a_{m-2}(E') - \frac {|\textbf{e}|(|\textbf{e}|-1)}2$$, следовательно, можно вместо $$a_{m-2}(E)$$ вычислять $$a_{m-2}(E')$$, поэтому в дальнейших рассуждениях предполагаем, что $$\deg \omega_{E'}\leq m-2$$ и $$\omega_E(t) =\sum\limits_{i=0}^{m-2} a_i(E)\binom {t+i}i$$, где $$a_i(E) \in \Z$$ $$(i=0,1,\dots,m-2)$$. Кроме того, предполагаем, что $$E$$ содержит не более двух ненулевых столбцов (следует отметить, что если в $$E$$ имеется единственный ненулевой столбец, то многочлен Гильберта $$\omega_E(t)$$ совпадает с минимальным элементом этого столбца). Предполагая, что первый столбец матрицы $$E$$ ненулевой, упорядочим его элементы и применим (13.14) при $$\tau=m-2$$. Поскольку число столбцов в $$E_1$$ (см. (13.14)) равно $$(m-1)$$, вычисление $$a_\tau(E_1)$$ можно свести к выбору минимальных элементов в столбцах матрицы $$E_1$$ (см. теорему 12.8(3)). Легко видеть, что такой выбор требует $$(m-1)b_1$$ элементарных операций, где $$b_1$$ — число строк матрицы $$E_1$$. Применяя (13.14) к $$E_2$$, сводим вычисление $$a_\tau(E_2)$$ (в правой части формулы (13.14)) к вычислению коэффициента $$a_2(E_{21})$$ многочлена Гильберта некоторой матрицы $$E_2$$, содержащей $$(m-1)$$ столбец (эта матрица получена добавлением некоторых дополнительных строк к $$E_1$$ ). Чтобы вычислить $$a_\tau(E_{21})$$, нужно не более $$(m-1)b_2$$ элементарных операций (здесь $$b_2$$ обозначает число строк матрицы $$E_{21}$$ ). Продолжаем применять (13.14), пока не получим матрицу с нулевым первым столбцом. По лемме 13.17 такой столбец можно отбросить, затем применяем (13.14) к новой матрице и т. д.
Асимптотическая сложность $$g(n,m)$$ описанного алгоритма не превосходит$$\begin{multiline*} n\log n+\hskip-10pt\smash[t]{\sum\limits^k_{\substack{i=1\\b_i\in\mathbb N\\b_1+\dots+b_k=n}}}\hskip-10pt b_im+g(n,m-1)\\ \leq2n\log n+n(m+m-1)+g(n,m-2)\leq \dots\\ \leq(m-1)n\log n+n(m+(m-1)+\dots+2)+g(n,1)\\ =(m-1)n\log n+n\binom{m+1}2\sim mn\log n. \end{multiline*}$$
А14. АЛГОРИТМ $$(E, n,m, a_{m-2})$$.
$$\begin{equation}\\ \text{Дано:\quad $ n\in\mathbb N;\ m\in\mathbb N $ ; $ n\!\times\!m $ -матрица $ E $ , такая, что $ \deg \omega_E\leq m-2 $ }\\ \text{Надо:\qquad $ a_{m-2}(E) $ .}\\ \text{Начало}\\ \text{ $ a_{m-2}:=0$} \\ \text{ $ r:= $ число нулевых столбцов матрицы $ E$} \\ \text{ $ m:=m-r $}\\ \text{$ E: $ удалить нулевые столбцы }\\ \text{сортировать строки по возрастанию элементов первого столбца}\\ \text{$\mathbb N_S:=0 $ }\\ \text{ $ i:= 1$} \\ \text{ $ E_0:= \emptyset$} \\ \text{ цикл пока $ i <n$} \\ \text{\qquad цикл пока $ e_{i1}=N_S $ и $ i\leq n $ }\\ \text{\qquad \qquad $ E_0:=E_0\cup (e_{i2},\dots,e_{im}) $ }\\ \text{\qquad \qquad $ i := i + 1 $ }\\ \text{\qquad конец цикла}\\ \text{\qquad $ N_R := e_{i1} $ }\\ \text{\qquad $ \textbf{a} := (a_1,\dots,a_{m-1}) $ , где $ a_i $ - минимальный элемент $ i $ -го столбца} \\ \text{\qquad \quad матрицы, состоящей из векторов из $ E_0 $ }\\ \text{\qquad $ E_0:=\textbf{a} $ }\\ \text{\qquad $ a_{m-2}:= a_{m-2} + |\textbf{a}|(N_R - N_S) $ }\\ \text{\qquad $ N_S := N_R $ }\\ \text{конец цикла}\\ \text{ $ E: $ удалить первый столбец}\\ \text{алгоритм A14 $ (E,n,m-1,b) $ }\\ \text{ $ a_{m-2}:= a_{m-2}+ b $ }\\ \text{Конец}\\ \end{equation}$$Теперь, пользуясь алгоритмом A14 и формулой (13.14), можно
найти
А15. АЛГОРИТМ $$(E, n,m, k, a_{m-k})$$.
$$\begin{equation} \text{Дано:\qquad $ n\in\mathbb N $ , $ m\in\mathbb N $ , $ k\in\mathbb N $ , $ k\geq2 $ , $ m\geq k $;}\\ \text{\qquad $ n\!\times\!m $ -матрица $ E $ , такая, что $ \deg\omega_E\leq m-k $ }\\ \text{Надо: \qquad $ a_{m-k}(E) $ .}\\ \text{Начало}\\ \text{$ a_{m-k}:=0 $} \\ \text{$ r:= $ число нулевых столбцов матрицы $ E $} \\ \text{$ m:=m-r $ }\\ \text{$ E: $ удалить нулевые столбцы }\\ \text{сортировать строки по возрастанию элементов первого столбца}\\ \text{$mathbb N_S:=0 $} \\ \text{$ i:= 1 $} \\ \text{$ E_0:= \emptyset $} \\ \text{цикл пока $ i<n $} \\ \text{\qquad цикл пока $ e_{i1}=N_S $ и $ i\leq n $ }\\ \text{\qquad \qquad $ E_0:=E_0\cup (e_{i2},\dots,e_{im}) $} \\ \text{\qquad \qquad $ i := i + 1 $ }\\ \text{\qquad конец цикла}\\ \text{\qquad $ N_R := e_{i1} $ }\\ \text{\qquad $ \textbf{a} := (a_1,\dots,a_{m-1}) $ , где $ a_i $ - минимальный элемент $ i $ -го столбца }\\ \text{\qquad \quad матрицы, состоящей из векторов из $ E_0 $} \\ \text{\qquad $ E_0:=\textbf{a} $} \\ \text{\qquad $ a_{m-2}:= a_{m-2} + |\textbf{a}|(N_R - N_S) $ }\\ \text{\qquad $ N_S := N_R $ }\\ \text{конец цикла}\\ \text{$ E: $ удалить первый столбец}\\ \text{алгоритм А14 $ (E,n,m-1,b) $ }\\ \text{$ a_{m-2}:= a_{m-2}+ b $} \\ \text{если $ k=2 $ , то алгоритм А14 $ (E, n, m, a_{m-2) $} \\ \text{иначе $ E: $ удалить нулевые столбцы }\\ \text{\qquad $ m:= $ число столбцов матрицы $ E $} \\ \text{\qquad $ N_S := 0 $} \\ \text{\qquad $ E_0:=\emptyset $} \\ \text{\qquad цикл для каждого ненулевого $ e_{i1} $ в порядке возрастания }\\ \text{\qquad \qquad $ N_R:= e_{i1} $ }\\ \text{\qquad \qquad $ E_0: $ добавить последовательность строк}\\ \text{\qquad \qquad \qquad $ \{ (e_{j2},\dots,e_{jm})\mid e_{j1}= N_S\} $} \\ \text{\qquad \qquad $ N_0 := $ число векторов в $ E_0 $ }\\ \text{\qquad \qquad алгоритм А15 $ (E_0,N_0,m-1,k-1,P) $ }\\ \text{\qquad \qquad $ a_{m-k}:= a_{m-k}+ (N_R - N_S)P $ }\\ \text{\qquad \qquad $ N_S:= N_R $} \\ \text{\qquad конец цикла}\\ \text{\qquad $ E: $ удалить первый столбец}\\ \text{\qquad алгоритм А15 $ (E,n,m-1,k-1,P) $ }\\ \text{\qquad $ a_{m-k}:= a_{m-k}+ P $ }\\ \text{конец если}\\ \text{Конец}\\ \end{equation}$$Завершая изложение теории размерностных многочленов, следует упомянуть размерностные многочлены от многих переменных, теория которых была заложена в статье и подробно изложена в монографии .
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.