%display latex
Objet d'étude : matrices $M$ de taille $m \times n$ à coefficients dans $k[x]$ avec $k$ un corps.
k = GF(7)
n = 2
kx.<x> = PolynomialRing(k)
M = Matrix(kx,n,n,lambda i,j: kx.random_element(degree=(1,3)))
'M=' + latex(M)
Mon rapport à ce sujet ?
sage/matrix/matrix_polynomial_dense.pyx
Définition: $k[x]$-module associé $\langle M \rangle$: ensemble des vecteurs qui sont des combinaisons $k[x]$-linéaires des lignes de $M$
c = [kx.random_element(degree=1) for i in range(n)]
v = c[0] * M.row(0) + c[1] * M.row(1)
LatexExpr(f'({latex(c[0])}) M_{{0,*}} + ({latex(c[1])}) M_{{1,*}} = {latex(v)} = v \\in \\langle M \\rangle')
Théorie classique des modules sur un anneau principal:
Remarque:
H, U = M.hermite_form(transformation=True)
pretty_print(LatexExpr(f'M={latex(M)}, H = UM = {latex(H)},'))
pretty_print(LatexExpr(f'U={latex(U)}'))
Hermite utile pour:
LatexExpr(f'\\langle M \\rangle \\cap (0,k[x]) = {latex(H[1:])}')
Hermite utile pour:
v = Matrix(1,n,lambda i,j: kx.random_element(degree=1)) * M
v = v.row(0)
pretty_print(LatexExpr(f'v = {latex(v)}'))
vp = v - (v[0]//H[0,0]) * H.row(0)
pretty_print(LatexExpr(f'v - (v_0 // H_{{0,0}}) H_{{0,*}} = {latex(vp)} \\rightarrow v\''))
vpp = vp - vp[1]//H[1,1] * H.row(1)
pretty_print(LatexExpr(f'v\' - (v\'_1 // H_{{1,1}}) H_{{1,*}} = {latex(vpp)}'))
S, U, V = M.smith_form(transformation=True)
pretty_print(LatexExpr(f'M={latex(M)}, S = UMV = {latex(S)}'))
pretty_print(LatexExpr(f'U={latex(U)}'))
pretty_print(LatexExpr(f'V={latex(V)}'))
Smith utile pour:
Calculer une base réduite $R \in k[x]^{m \times n}$ de $\langle M \rangle$,
i.e. telle que les degrés des lignes de $R$ sont minimales parmi toutes les bases
M = Matrix(kx,3,2,[
[5*x^3 + 3*x^2 + 3*x + 5, 3*x^3 + 6*x^2 + 5*x + 1],
[ 6*x^2 + 3*x + 4, 2*x^3 + 2*x^2 + 6],
[ x + 6, 4*x + 3]])
R, U = M.weak_popov_form(ordered=True, transformation = True)
pretty_print(LatexExpr(f'M={latex(M)} \\rightarrow_{{réduction}} R=UM={latex(R)}'))
pretty_print(LatexExpr(f'U={latex(U)}'))
def argmax(L):
l = len(L)
index = -1
currentMax = -1
for i in range(l):
if (L[i] >= currentMax):
currentMax = L[i]
index = i
return index
def latex_pivots(M):
m,n = M.dimensions()
begin = r'\left(\begin{array}{'
for i in range(n):
begin += 'r'
begin += '}\n'
corps = ''
for i in range(m):
pivot_index = argmax([M[i,j].degree() for j in range(n)])
for j in range(n-1):
if (j == pivot_index):
corps += r' \color{{red}}{{[{}]}} &'.format(M[i,j].degree())
else:
corps += r' [{}] &'.format(M[i,j].degree())
j=n-1
if (j == pivot_index):
corps += r' \color{{red}}{{[{}]}} \\ '.format(M[i,j].degree())
else:
corps += r' [{}] \\'.format(M[i,j].degree())
end = r'\end{array}\right)'
return begin + corps + end
def add_multiple_of_row_c(M, i, j, s, start_col):
for c in range(start_col,M.ncols()):
M[i,c] = M[i,c] + s*M[j,c]
def _weak_popov_form_step(M_in, transformation=False):
M = M_in.__copy__()
m, n = M.dimensions()
R = M.base_ring()
one = R.one()
Mlist = [M_in]
transformationList = []
# initialise to_row and conflicts list
to_row = [[] for i in range(n)]
conflicts = []
for i in range(m):
bestp = -1
best = -1
for c in range(n):
d = M[i,c].degree()
if d >= best:
bestp = c
best = d
if best >= 0:
to_row[bestp].append((i,best))
if len(to_row[bestp]) > 1:
conflicts.append(bestp)
# while there is a conflict, do a simple transformation
while conflicts:
c = conflicts.pop()
row = to_row[c]
i,ideg = row.pop()
j,jdeg = row.pop()
if jdeg > ideg:
i,j = j,i
ideg,jdeg = jdeg,ideg
coeff = - M[i,c].lc() / M[j,c].lc()
s = coeff * one.shift(ideg - jdeg)
add_multiple_of_row_c(M,i, j, s, 0)
Mlist.append(M.__copy__())
transformationList.append([i,j,s])
row.append((j,jdeg))
bestp = -1
best = -1
for c in range(n):
d = M[i,c].degree()
if d >= best:
bestp = c
best = d
if best >= 0:
to_row[bestp].append((i,best))
if len(to_row[bestp]) > 1:
conflicts.append(bestp)
return Mlist, transformationList
Ms, reductions = _weak_popov_form_step(M)
@interact
def g(k=range(len(reductions))):
red = reductions[k]
Mfrom = Ms[k]
Mto = Ms[k+1]
l = LatexExpr(latex_pivots(Mfrom))
l += LatexExpr(f'\\xrightarrow{{ M_{{{red[0]}}} \\leftarrow M_{{{red[0]}}} - ({latex(red[2])}) M_{{{red[1]}}} }}')
l += LatexExpr(latex_pivots(Mto))
pretty_print(l)
Interactive function <function g at 0x7f843dcba820> with 1 widget k: Dropdown(description='k', options=(0, 1…
N = Matrix(kx,2,1,lambda i,j: kx.random_element(degree=5))
Ns, reductions2 = _weak_popov_form_step(N)
@interact
def g(k=range(len(reductions2))):
red = reductions2[k]
Mfrom = Ns[k]
Mto = Ns[k+1]
l = LatexExpr(latex(Mfrom))
l += LatexExpr(f'\\xrightarrow{{ M_{{{red[0]}}} \\leftarrow M_{{{red[0]}}} - ({latex(red[2])}) M_{{{red[1]}}} }}')
l += LatexExpr(latex(Mto))
pretty_print(l)
Interactive function <function g at 0x7f843db69dc0> with 1 widget k: Dropdown(description='k', options=(0, 1…
Propriétés de $G = \textrm{left_gcd}(M,N)$:
n = 2
M = Matrix(kx,n,n,lambda i,j: kx.random_element(degree=2))
N = Matrix(kx,n,n,lambda i,j: kx.random_element(degree=2))
G, T = M.stack(N).weak_popov_form(transformation=True)
G = G[0:n]
U = T[0:n,0:n]
V = T[0:n,n:2*n]
pretty_print(LatexExpr(f'G = {latex(G)}'))
pretty_print(LatexExpr(f'{latex(U)} M + {latex(V)} N = G'))
C = T^(-1)
C1 = C[0:n,0:n]
C2 = C[n:2*n,0:n]
C1 * G == M
C2 * G == N
pretty_print(LatexExpr(f'{latex(C1)} G = M'))
pretty_print(LatexExpr(f'{latex(C2)} G = N'))
Codes de Reed-Solomon:
Si
Alors
Application au décodage de codes correcteurs
Codes de Reed-Solomon entrelacés:
Si
Alors
Source: HDR Pascal Giorgi
sage/matrix/matrix_polynomial_dense.pyx
Auteurs: Vincent Neiger, Johan Rosenkilde, Kwankyu Lee
Fonctions de calculs:
Fonctions de vérification: