تمثيل الماترويد

في النظرية الرياضية للماترويدات ، يُعرَّف تمثيل الماترويد بأنه مجموعة من المتجهات التي تتطابق علاقة استقلالها الخطي مع علاقة استقلال ماترويد مُعطى. وتُشابه تمثيلات الماترويدات تمثيلات الزمر ؛ إذ يُقدِّم كلا النوعين من التمثيل بنى جبرية مجردة (الماترويدات والزمر على التوالي) مع وصف ملموس باستخدام الجبر الخطي .

الماترويد الخطي هو ماترويد له تمثيل، والماترويد الخطي F ( للحقل F ) هو ماترويد له تمثيل باستخدام فضاء متجهي على F. تدرس نظرية تمثيل الماترويد وجود التمثيلات وخصائص الماترويدات الخطية .

ماترويد (محدود)${\displaystyle (E,{\mathcal {I}})}$يتم تعريفها بواسطة مجموعة منتهية${\displaystyle E}$(عناصر الماترويد) وعائلة غير فارغة${\displaystyle {\mathcal {I}}}$من المجموعات الفرعية لـ${\displaystyle E}$تُسمى هذه المجموعات بالمجموعات المستقلة للماترويد. ويُشترط أن تُحقق الخصائص التالية: أن كل مجموعة جزئية من مجموعة مستقلة هي نفسها مستقلة، وأنه إذا كانت مجموعة مستقلة واحدة${\displaystyle A}$أكبر من مجموعة مستقلة ثانية${\displaystyle B}$ثم يوجد عنصر${\displaystyle x\in A\setminus B}$يمكن إضافته إلى${\displaystyle B}$لتشكيل مجموعة مستقلة أكبر. كان أحد الأمثلة المحفزة الرئيسية في صياغة الماترويدات هو مفهوم الاستقلال الخطي للمتجهات في فضاء متجهي : إذا${\displaystyle E}$هي مجموعة منتهية أو مجموعة متعددة من المتجهات، و${\displaystyle {\mathcal {I}}}$هي عائلة المجموعات الفرعية المستقلة خطيًا من${\displaystyle E}$، ثم${\displaystyle (E,{\mathcal {I}})}$هو ماترويد. ^{[ 1 ] [ 2 ]}

وبشكل أعم، إذا${\displaystyle (E,{\mathcal {I}})}$أي ماترويد، فهو تمثيل لـ${\displaystyle (E,{\mathcal {I}})}$يمكن تعريفها كدالة${\displaystyle f}$تلك الخرائط${\displaystyle E}$إلى فضاء متجهي${\displaystyle V}$، مع خاصية أن مجموعة جزئية${\displaystyle A}$ل${\displaystyle E}$تكون مستقلة إذا وفقط إذا${\displaystyle f|_{A}}$هو حقني و${\displaystyle f(A)}$مستقل خطيًا. يُطلق على الماترويد ذي التمثيل اسم ماترويد خطي، وإذا${\displaystyle V}$إذا كان فضاءً متجهيًا على الحقل F، فإن الماترويد يُسمى ماترويدًا خطيًا على F. وبالتالي، فإن الماترويدات الخطية هي تحديدًا الماترويدات المتماثلة مع الماترويدات المعرفة من مجموعات أو مجموعات متعددة من المتجهات.${\displaystyle f}$تكون العلاقة أحادية إذا وفقط إذا كانت الماترويد الأساسية بسيطة (لا تحتوي على مجموعات مرتبطة بعنصرين). يمكن أيضًا وصف تمثيلات الماترويد بشكل أكثر تحديدًا باستخدام المصفوفات على حقل F ، مع عمود واحد لكل عنصر من عناصر الماترويد، وتكون مجموعة العناصر مستقلة في الماترويد إذا وفقط إذا كانت مجموعة أعمدة المصفوفة المقابلة مستقلة خطيًا. تُعطى دالة رتبة الماترويد الخطي برتبة المصفوفات الفرعية لهذه المصفوفة، أو بشكل مكافئ ببعد الامتداد الخطي لمجموعات فرعية من المتجهات . ^{[ 3 ]}

ليست كل الماترويدات خطية؛ فماترويد فاموس ذو الثمانية عناصر هو أحد أصغر الماترويدات التي لا يمكن تمثيلها على جميع الحقول. ^{[ 4 ]} إذا كان الماترويد خطيًا، فقد يكون قابلاً للتمثيل على بعض الحقول وليس جميعها. على سبيل المثال، الماترويد ذو الرتبة الثالثة والمكون من تسعة عناصر، والمُعرَّف بتكوين بيرلز، قابل للتمثيل على الأعداد الحقيقية ولكنه غير قابل للتمثيل على الأعداد النسبية .

الماترويدات الثنائية هي الماترويدات التي يمكن تمثيلها على الحقل المنتهي GF(2) ؛ وهي تحديدًا الماترويدات التي لا تمتلك الماترويد المنتظم.${\displaystyle U{}_{4}^{2}}$كعنصر ثانوي . ^{[ 5 ]} الماترويدات أحادية المعامل أو المنتظمة هي الماترويدات التي يمكن تمثيلها على جميع الحقول؛ ^{[ 6 ]} ويمكن وصفها بأنها الماترويدات التي لا تحتوي على أي من${\displaystyle U{}_{4}^{2}}$، أو مستوى فانو (مصفوفة ثنائية ذات سبعة عناصر)، أو المصفوفة الثنائية لمستوى فانو كمصفوفات فرعية. ^{[ 5 ] [ 7 ]} وبدلاً من ذلك، تكون المصفوفة منتظمة إذا وفقط إذا أمكن تمثيلها بمصفوفة أحادية المعامل تمامًا . ^{[ 8 ]}

تنص فرضية روتا على أنه لكل حقل منتهٍ F ، يمكن تمييز الماترويدات الخطية F بمجموعة منتهية من المحددات الصغرى المحظورة، على غرار التوصيفات المذكورة أعلاه للماترويدات الثنائية والمنتظمة. ^{[ 9 ]} وحتى عام 2012، لم تُثبت هذه الفرضية إلا للحقول التي تحتوي على أربعة عناصر أو أقل. ^{[ 5 ] [ 10 ] [ 11 ] [ 12 ]} أما بالنسبة للحقول غير المنتهية (مثل حقل الأعداد الحقيقية )، فلا يمكن تحقيق مثل هذا التوصيف. ^{[ 13 ]}

لكل حقل عددي جبري ولكل حقل منتهٍ F يوجد ماترويد M يكون F هو الحقل الفرعي الأدنى لإغلاقه الجبري الذي يمكن تمثيل M عليه: يمكن اعتبار M من الرتبة 3. ^{[ 14 ]}

تُعرَّف المجموعة المميزة للماترويد الخطي بأنها مجموعة خصائص الحقول التي يكون خطيًا عليها. ^{[ 15 ]} لكل عدد أولي p ، يوجد عدد لا نهائي من الماترويدات التي تكون مجموعتها المميزة هي مجموعة العناصر المفردة { p }، ^{[ 16 ]} ولكل مجموعة منتهية من الأعداد الأولية، يوجد ماترويد تكون مجموعته المميزة هي المجموعة المنتهية المعطاة. ^{[ 17 ]}

إذا كانت المجموعة المميزة للماترويد لانهائية، فإنها تحتوي على الصفر؛ وإذا كانت تحتوي على الصفر، فإنها تحتوي على جميع الأعداد الأولية باستثناء عدد محدود منها. ^{[ 18 ]} ومن ثم، فإن المجموعات المميزة الممكنة الوحيدة هي المجموعات المنتهية التي لا تحتوي على الصفر، والمجموعات المنتهية جزئيًا التي تحتوي على الصفر. ^{[ 19 ]} في الواقع، توجد جميع هذه المجموعات. ^{[ 20 ]}

مصفوفة موحدة${\displaystyle U{}_{n}^{r}}$لديه${\displaystyle n}$تتكون العناصر، ومجموعاتها المستقلة من جميع المجموعات الفرعية حتى${\displaystyle r}$من العناصر. يمكن تمثيل المصفوفات المنتظمة بمجموعات من المتجهات في وضع عام في${\displaystyle r}$فضاء متجهي ذو أبعاد n. يجب أن يكون مجال التمثيل كبيرًا بما يكفي لوجوده${\displaystyle n}$المتجهات في موضع عام في هذا الفضاء المتجهي، لذا فإن المصفوفات المنتظمة تكون خطية بالنسبة لجميع الحقول F باستثناء عدد محدود منها . ^{[ 21 ]} وينطبق الشيء نفسه على مصفوفات التقسيم ، وهي المجاميع المباشرة للمصفوفات المنتظمة، حيث أن المجموع المباشر لأي مصفوفتين خطيتين بالنسبة لـ F هو نفسه خطي بالنسبة لـ F.

الماترويد الرسومي هو الماترويد المُعرَّف من حواف رسم بياني غير موجه، وذلك بتحديد مجموعة من الحواف على أنها مستقلة إذا وفقط إذا لم تحتوي على دورة . كل ماترويد رسومي منتظم، وبالتالي فهو خطي بالنسبة ^للحقل F لكل حقل F. ^{[ 8} ]

تصف مصفوفات الصلابة درجات حرية الوصلات الميكانيكية المكونة من قضبان صلبة متصلة عند أطرافها بمفاصل مرنة. يمكن وصف وصلة من هذا النوع على أنها رسم بياني، حيث يمثل كل قضيب حافة، ويمثل كل مفصل رأسًا. بالنسبة للوصلات أحادية البعد، تكون مصفوفات الصلابة هي نفسها مصفوفات الرسم البياني. يمكن تعريف مصفوفات الصلابة ذات الأبعاد الأعلى باستخدام مصفوفات من الأعداد الحقيقية ذات بنية مشابهة لبنية مصفوفة الوقوع للرسم البياني الأساسي، وبالتالي فهي${\displaystyle \mathbb {R} }$-خطي. ^{[ 22 ] [ 23 ]}

مثل المصفوفات المنتظمة والمصفوفات التقسيمية، فإن المصفوفات الغامويدية ، وهي مصفوفات تمثل إمكانية الوصول في الرسوم البيانية الموجهة ، تكون خطية على أي حقل كبير بما فيه الكفاية. وبشكل أكثر تحديدًا، فإن المصفوفة الغامويدية التي${\displaystyle n}$يمكن تمثيل العناصر فوق كل حقل يحتوي على الأقل${\displaystyle 2^{n}}$العناصر. ^{[ 24 ]}

الماترويدات الجبرية هي ماترويدات مُعرَّفة من مجموعات عناصر امتداد حقل باستخدام مفهوم الاستقلال الجبري . كل ماترويد خطي هو ماترويد جبري، وبالنسبة للحقول ذات الخاصية الصفرية (مثل الأعداد الحقيقية) تتطابق الماترويدات الخطية والجبرية، ولكن بالنسبة للحقول الأخرى قد توجد ماترويدات جبرية غير خطية. ^{[ 25 ]}