Стр. 5 - Е.Ю. Алехова - Исследование кластеризуемости строк больших разреженных матриц над GF(2)

ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012 41
1
1 1 1
0 0 1
! !
! .
1 ( )! ( )!
!
l
i k
l k k k
i i i
n i m
l l
l
i n n n i l k i l k m m n
m m
l
−
=
− − −
= = =
⎡ ⎤ ⎛ ⎞ − ⎜ ⎟ ⎢
⎥
⎝ ⎠ ⎣ ⎦
= =
⎡ ⎤ ⎡ ⎤ ⎡ ⎤ ⎛ ⎞ ⎛ ⎞ − − − − ⎛ ⎞ ⎜ ⎟ ⎜ ⎟ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ − ⎛ ⎞ ⎜ ⎟ ⎝ ⎠ ⎝ ⎠ ⎣ ⎦ ⎣ ⎦ ⎢ ⎥ ⎜ ⎟ ⎝ ⎠ ⎝ ⎠ ⎣ ⎦
∏
∏ ∏ ∏
(15)
Оценим
1
1
1
1
( 1)
1 1 1 1.
2
k
k
i
i
i
i k k
n n n
m m m
−
−
−
=
⎡ ⎤
⎢ ⎥ −
⎢ ⎥
− ≈ − = − ≈
⎢ ⎥ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞
⎢ ⎥ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟
⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎣ ⎦
∑
∏
Используя эту оценку, можно упростить выражение (15):
1
1
! ! .
( )!
( )! 1
k
k k
i
l l
n
l k
n i m
l k n m
m
−
=
≈
⎡ ⎤ ⎛ ⎞
− ⎢ ⎥ ⎜ ⎟
⎛ ⎞ ⎢ ⎥ ⎝ ⎠
− −
⎜ ⎟ ⎢ ⎥ ⎛ ⎞
⎝ ⎠ ⎢ ⎥ ⎜ ⎟
⎝ ⎠ ⎣ ⎦
∏
(16)
Рассмотрим оставшийся сомножитель из числителя выражения (13):
1
1
0 1 .
! !
k
k
k
i
i k
s s
i s m m i
m n k k
k m
−
−
=
=
⎡ ⎤ ⎛ ⎞ ⎡ ⎤ ⎛ ⎞
− ⎛ ⎞ ⎛ ⎞ ⎢ ⎥ ⎜ ⎟ ⎢ ⎥ ⎜ ⎟
⎜ ⎟ ⎝ ⎠ ⎜ ⎟ ⎣ ⎦ ⎝ ⎠ ⎢ ⎥
= = −
⎝ ⎠ ⎜ ⎟ ⎢ ⎥ ⎛ ⎞
⎜ ⎟ ⎢ ⎥ ⎜ ⎟ ⎝ ⎠ ⎝ ⎠ ⎣ ⎦
∏
∏ (17)
Поскольку разница между m и s менее значительна, чем между m
и n, с выражением (17) нельзя поступить так же, как с (15).
Подставим в выражение (13) полученные соотношения:
1 ! 1
!
( )!
k
k
k
i k
n s
k
m m s
l k k m l i
p n k n n
l k m m m
l
−
=
⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞
− ⎜⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎡ ⎤ ⎛ ⎞ ⎝ ⎠ ⎝ ⎠
⎜ ⎟ ⎜ ⎟ ⎢ ⎥ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟
− ⎝⎠ ⎝ ⎠ ⎝ ⎠ ⎢ ⎥ ≈ = − =
⎢ ⎥ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞
− ⎜ ⎟ ⎜ ⎟ ⎢ ⎥ ⎜ ⎟ ⎜ ⎟ ⎝ ⎠ ⎝ ⎠ ⎣ ⎦ ⎝ ⎠ ⎜ ⎟
⎜ ⎟
⎝ ⎠
∏