الشكل الطبيعي للهيرميت

مصفوفة${\displaystyle A\in \mathbb {Z} ^{m\times n}}$له شكل هيرميت طبيعي (صف)${\displaystyle H}$إذا كانت هناك مصفوفة مربعة أحادية المعيار${\displaystyle U}$بحيث${\displaystyle H=UA}$و: ^{[ 4 ] [ 5 ] [ 6 ]}

1. ${\displaystyle H}$هو مثلث علوي (أي،${\displaystyle h_{ij}=0}$ل${\displaystyle i>j}$)، وأي صفوف من الأصفار تقع أسفل أي صف آخر.
2. المعامل الرئيسي (أول إدخال غير صفري من اليسار، ويسمى أيضًا المحور ) لصف غير صفري يكون دائمًا على يمين المعامل الرئيسي للصف الذي فوقه؛ علاوة على ذلك، فهو موجب.
3. العناصر الموجودة أسفل المحاور تساوي صفرًا، والعناصر الموجودة أعلى المحاور غير سالبة وأصغر تمامًا من المحور.

الشرط الثالث ليس معيارياً بين المؤلفين، فمثلاً، تشترط بعض المصادر أن تكون القيم غير المحورية غير موجبة ^{[ 7 ] [ 8 ]} أو لا تفرض أي قيود على إشارتها ^{[ 9 ]} . ومع ذلك، فإن هذه التعريفات متكافئة باستخدام مصفوفة أحادية المعامل مختلفة.${\displaystyle U}$المصفوفة أحادية المعامل هي مصفوفة مربعة من الأعداد الصحيحة يكون محددها إما 1 أو -1 (وبالتالي قابلة للعكس ). في الواقع، المصفوفة أحادية المعامل قابلة للعكس على مجموعة الأعداد الصحيحة، كما يتضح، على سبيل المثال، من قاعدة كرامر .

مصفوفة${\displaystyle A\in \mathbb {Z} ^{m\times n}}$له شكل هيرميت طبيعي (عمودي)${\displaystyle H}$إذا كانت هناك مصفوفة مربعة أحادية المعيار${\displaystyle U}$أين${\displaystyle H=AU}$و${\displaystyle H}$تتضمن القيود التالية: ^{[ 8 ] [ 10 ]}

1. ${\displaystyle H}$هو مثلث سفلي (${\displaystyle h_{ij}=0}$ل${\displaystyle i<j}$) وأي أعمدة من الأصفار تقع على اليمين.
2. المعامل الرئيسي (أول إدخال غير صفري من الأعلى، ويسمى أيضًا المحور ) لعمود غير صفري يكون دائمًا أقل بكثير من المعامل الرئيسي للعمود الذي يسبقه؛ علاوة على ذلك، فهو موجب.
3. العناصر الموجودة على يمين المحاور تساوي صفرًا، والعناصر الموجودة على يسار المحاور غير سالبة وأصغر تمامًا من المحور.

لاحظ أن تعريف نمط الصف له مصفوفة أحادية المعامل${\displaystyle U}$مضاعفة${\displaystyle A}$على اليسار (بمعنى${\displaystyle U}$يتصرف على صفوف${\displaystyle A}$)، بينما يكون لتعريف نمط العمود تأثير المصفوفة أحادي المعامل على أعمدة${\displaystyle A}$إن التعريفين للأشكال الطبيعية لهيرميت هما ببساطة منقولان لبعضهما البعض.

في الأمثلة أدناه، H هو الشكل الطبيعي لهرميت للمصفوفة A ، و U هي مصفوفة أحادية المعامل بحيث UA = H.$${\displaystyle A={\begin{pmatrix}3&3&1&4\\0&1&0&0\\0&0&19&16\\0&0&0&3\end{pmatrix}}\qquad H={\begin{pmatrix}3&0&1&1\\0&1&0&0\\0&0&19&1\\0&0&0&3\end{pmatrix}}\qquad U=\left({\begin{array}{rrrr}1&-3&0&-1\\0&1&0&0\\0&0&1&-5\\0&0&0&1\end{array}}\right)}$$

$${\displaystyle A={\begin{pmatrix}2&3&6&2\\5&6&1&6\\8&3&1&1\end{pmatrix}}\qquad H=\left({\begin{array}{rrrr}1&0&50&-11\\0&3&28&-2\\0&0&61&-13\end{array}}\right)\qquad U=\left({\begin{array}{rrr}9&-5&1\\5&-2&0\\11&-6&1\end{array}}\right)}$$

إذا كان للمصفوفة A صف واحد فقط، فإن H إما = A أو H = − A ، اعتمادًا على ما إذا كان للصف الوحيد من A معامل رئيسي موجب أو سالب.

توجد العديد من الخوارزميات لحساب الشكل الطبيعي لهيرميت، ويعود تاريخها إلى عام 1851. إحدى هذه الخوارزميات موصوفة في ^{[ 13 ] : 43-45.} ولكن في عام 1979 فقط تم تطوير خوارزمية لحساب الشكل الطبيعي لهيرميت تعمل في وقت متعدد الحدود بشكل قوي ؛ ^{[ 14 ]} أي أن عدد الخطوات اللازمة لحساب الشكل الطبيعي لهيرميت محدود من الأعلى بكثير حدود في أبعاد مصفوفة الإدخال، والمساحة التي تستخدمها الخوارزمية (الأعداد الوسيطة) محدودة بكثير حدود في حجم الترميز الثنائي للأعداد في مصفوفة الإدخال.

تعتمد إحدى فئات الخوارزميات على طريقة الحذف الغاوسي ، حيث تُستخدم مصفوفات أولية خاصة بشكل متكرر. ^{[ 11 ] [ 15 ] [ 16 ]} كما يمكن استخدام خوارزمية LLL لحساب الشكل الطبيعي لهيرميت بكفاءة. ^{[ 17 ] [ 18 ]}

تتخذ الشبكة النموذجية في R ⁿ الشكل التالي${\textstyle L=\left\{\left.\sum _{i=1}^{n}\alpha _{i}\mathbf {a} _{i}\;\right\vert \;\alpha _{i}\in {\textbf {Z}}\right\}}$حيث تنتمي العناصر aᵢ إلى Rⁿ . ^إذا كانت أعمدة المصفوفة A هي العناصر aᵢ _، فيمكن ربط الشبكة بأعمدة المصفوفة، وتُسمى A أساسًا لـ L. ولأن شكل هيرميت الطبيعي فريد، فإنه يُمكن استخدامه للإجابة عن العديد من الأسئلة المتعلقة بوصفين للشبكة. فيما يلي _،${\displaystyle L_{A}}$يرمز إلى الشبكة المولدة من أعمدة المصفوفة A. ولأن الأساس يقع في أعمدة المصفوفة A ، يجب استخدام الشكل الطبيعي لهرميت ذي النمط العمودي. بفرض وجود أساسين لشبكة، A و A'تتمثل مشكلة التكافؤ في تحديد ما إذا كان${\displaystyle L_{A}=L_{A'}.}$يمكن القيام بذلك عن طريق التحقق مما إذا كان الشكل الطبيعي لهيرميت ذو النمط العمودي لـ A و A'تكون متطابقة حتى إضافة صفر من الأعمدة. هذه الاستراتيجية مفيدة أيضًا لتحديد ما إذا كانت الشبكة مجموعة جزئية (${\displaystyle L_{A}\subseteq L_{A'}}$إذا وفقط إذا${\displaystyle L_{[A\mid A']}=L_{A'}}$)، تحديد ما إذا كان المتجه v موجودًا في شبكة (${\displaystyle v\in L_{A}}$إذا وفقط إذا${\displaystyle L_{[v\mid A]}=L_{A}}$), ولحسابات أخرى. ^{[ 19 ]}

يملك النظام الخطي Ax = b حلاً صحيحاً x إذا وفقط إذا كان للنظام Hy = b حلاً صحيحاً y، حيث y = U ⁻¹ x و H هي الصيغة الطبيعية العمودية لهرميت للمصفوفة A. يُعد التحقق من أن Hy = b يملك حلاً صحيحاً أسهل من التحقق من أن Ax = b لأن المصفوفة H مثلثية. ^{[ 11 ] : 55}