ในคณิตศาสตร์เชิงการจัดเรียง (combinatorics) matroid / ˈ m eɪ t r ɔɪ d /คือโครงสร้างที่สรุปและขยายแนวคิดเรื่องความเป็นอิสระเชิงเส้นในปริภูมิเวกเตอร์มีวิธีการกำหนด matroid ในเชิงสัจพจน์ หลายวิธีที่เทียบเท่ากัน วิธีที่สำคัญที่สุดคือการกำหนดในแง่ของ: เซตอิสระ; ฐานหรือวงจร; ฟังก์ชันอันดับ; ตัวดำเนินการปิด; และเซตปิดหรือระนาบในภาษาของเซตที่มีลำดับบางส่วน matroid แบบง่ายจำกัดเทียบเท่ากับ แลตทิซ ทาง เรขาคณิต

ทฤษฎี Matroid ยืมคำศัพท์จากพีชคณิตเชิงเส้นและทฤษฎีกราฟอย่างกว้างขวาง เนื่องจากเป็นนามธรรมของแนวคิดต่างๆ ที่มีความสำคัญอย่างยิ่งในสาขาเหล่านี้ Matroid ได้ถูกนำไปประยุกต์ใช้ในเรขาคณิตโทโพโลยีการเพิ่มประสิทธิภาพเชิงรวมทฤษฎีเครือข่ายและทฤษฎีการเข้ารหัส^{[ 1 ] [ 2 ]}

มีหลาย วิธีที่สามารถกำหนดนิยามของเมทริกซ์ ( จำกัด ) ได้^{[ a ]}

ในแง่ของความเป็นอิสระ เมทริกซ์จำกัดคือคู่โดยที่เป็นเซตจำกัด (เรียกว่าเซตพื้นฐาน ) และเป็นตระกูลของเซตย่อยของ(เรียกว่าเซตอิสระ ) ที่มีคุณสมบัติดังต่อไปนี้: ^{[ 4 ]}${\displaystyle M}$${\displaystyle (E,{\คณิตศาสตร์ {I}})}$${\displaystyle E}$${\displaystyle {\คณิตศาสตร์ {I}}}$${\displaystyle E}$

• (I1) เซตว่างเป็นอิสระ กล่าวคือ.${\displaystyle \emptyset \in {\mathcal {I}}}$

• (I2) เซตย่อยทุกเซตของเซตอิสระเป็นเซตอิสระ กล่าวคือ สำหรับแต่ละถ้าแล้วสิ่งนี้บางครั้งเรียกว่าคุณสมบัติสืบทอดหรือคุณสมบัติปิดลง${\displaystyle A'\subseteq A}$${\displaystyle A\in {\mathcal {I}}}$${\displaystyle A'\in {\mathcal {I}}}$

• (I3) ถ้าและเป็นเซตอิสระสองเซต (กล่าวคือ แต่ละเซตเป็นอิสระ) และมีสมาชิกมากกว่าแล้วจะมี อยู่จริงที่ทำให้เป็นเซตอิสระ คุณสมบัตินี้บางครั้งเรียกว่าคุณสมบัติการเพิ่มจำนวนหรือคุณสมบัติการแลกเปลี่ยนเซตอิสระ (ดูทฤษฎีบทการแลกเปลี่ยนของสไตน์นิทซ์ )${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$${\displaystyle x\in A\setminus B}$${\displaystyle B\cup \{x\}}$

คุณสมบัติสองข้อแรกกำหนดโครงสร้างเชิงการจัดเรียงที่เรียกว่าระบบความเป็นอิสระ (หรือคอมเพล็กซ์เชิงซิมพลิเชียลนามธรรม ) อันที่จริง สมมติว่า (I2) คุณสมบัติ (I1) เทียบเท่ากับข้อเท็จจริงที่ว่าอย่างน้อยหนึ่งเซตย่อยของเป็นอิสระ กล่าวคือ ${\displaystyle E}$${\displaystyle {\mathcal {I}}\neq \emptyset }$

เซตย่อยของเซตพื้นฐานที่ไม่เป็นอิสระ เรียกว่าเซตขึ้นอยู่ ${\displaystyle E}$

เซตอิสระสูงสุด – กล่าวคือ เซตอิสระที่ขึ้นอยู่กับการเพิ่มสมาชิกใดๆ เข้าไปใน– เรียกว่าฐานสำหรับแมทรอยด์ ${\displaystyle E}$

วงจรในแมทรอยด์คือเซตย่อยที่ขึ้นอยู่กันขั้นต่ำของ– นั่นคือเซตที่ขึ้นอยู่กันซึ่งเซตย่อยที่แท้จริงทั้งหมดเป็นอิสระต่อกัน คำนี้เกิดขึ้นเนื่องจากวงจรของ แมทรอย ด์กราฟิกเป็นวัฏจักรในกราฟที่สอดคล้องกัน^{[ 4 ]}${\displaystyle M}$${\displaystyle E}$

เซตที่ขึ้นอยู่กัน ฐาน หรือวงจรของแมทรอยด์จะกำหนดลักษณะของแมทรอยด์ได้อย่างสมบูรณ์: เซตจะเป็นอิสระก็ต่อเมื่อไม่ขึ้นอยู่กัน ก็ต่อเมื่อเป็นเซตย่อยของฐาน และก็ต่อเมื่อไม่มีวงจร การรวบรวมเซตที่ขึ้นอยู่กัน ฐาน และวงจรแต่ละชุดมีคุณสมบัติง่ายๆ ที่สามารถนำมาใช้เป็นสัจพจน์สำหรับแมทรอยด์ได้ ตัวอย่างเช่น อาจกำหนดแมทรอยด์ให้เป็นคู่โดยที่เป็นเซตจำกัดดังที่กล่าวมาแล้ว และเป็นการรวบรวมเซตย่อยของเรียกว่าฐานซึ่งมีคุณสมบัติดังต่อไปนี้: ^{[ 4 ]}${\displaystyle M}$${\displaystyle (E,{\mathcal {B}})}$${\displaystyle E}$${\displaystyle {\mathcal {B}}}$${\displaystyle E}$

• (B1) ไม่ว่างเปล่า${\displaystyle {\mathcal {B}}}$

• (B2) ถ้าและเป็นสมาชิกที่แตกต่างกันของและแล้วจะมีองค์ประกอบ อยู่ซึ่ง${\displaystyle A}$${\displaystyle B}$${\displaystyle {\mathcal {B}}}$${\displaystyle a\in A\smallsetminus B}$${\displaystyle b\in B\smallsetminus A}$${\displaystyle (A\smallsetminus \{a\})\cup \{b\}\in {\mathcal {B}}}$

คุณสมบัตินี้ (B2) เรียกว่าคุณสมบัติการแลกเปลี่ยนฐานจากคุณสมบัตินี้จึงสรุปได้ว่าไม่มีสมาชิกใดในกลุ่มที่สามารถเป็นเซตย่อยแท้ของกลุ่มอื่นได้ ${\displaystyle {\mathcal {B}}}$

เป็นผลลัพธ์พื้นฐานของทฤษฎี matroid ซึ่งคล้ายคลึงโดยตรงกับทฤษฎีฐานที่คล้ายกันในพีชคณิตเชิงเส้นที่ว่าฐานสองฐานใดๆ ของ matroid จะมีจำนวนสมาชิกเท่ากัน จำนวนนี้เรียกว่าอันดับของmatroidถ้าmatroid บนและเป็นเซตย่อยของmatroid แล้ว matroid บนสามารถกำหนดได้โดยพิจารณาว่าเซตย่อยของเป็นอิสระก็ต่อเมื่อมันเป็นอิสระในmatroid เท่านั้น ซึ่งทำให้เราสามารถพูดถึงsubmatroidและอันดับของเซตย่อยใดๆ ของmatroid ได้ อันดับของเซตย่อยกำหนดโดยฟังก์ชันอันดับของ matroid ซึ่งมีคุณสมบัติดังต่อไปนี้: ^{[ 4 ]}${\displaystyle M}$${\displaystyle M}$${\displaystyle M}$${\displaystyle E}$${\displaystyle A}$${\displaystyle E}$${\displaystyle A}$${\displaystyle A}$${\displaystyle M}$${\displaystyle E}$${\displaystyle A}$${\displaystyle r(A)}$

• (R1) ค่าของฟังก์ชันอันดับจะเป็นจำนวนเต็มที่ ไม่เป็นลบ เสมอ

• (R2) สำหรับเซตย่อยใดๆเรามี${\displaystyle A\subset E}$${\displaystyle r(A)\leq |A|}$

• (R3) สำหรับเซตย่อยสองเซตใดๆเรามี: นั่นคือ อันดับเป็นฟังก์ชันย่อยโมดูลาร์${\displaystyle A,B\subset E}$${\displaystyle r(A\cup B)+r(A\cap B)\leq r(A)+r(B)}$

• (R4) สำหรับเซตและสมาชิก ใดๆ เรามี: จากอสมการแรกจะเห็นได้โดยทั่วไปว่า ถ้าแล้วนั่นคือ อันดับเป็นฟังก์ชันเอกภาค${\displaystyle A}$${\displaystyle x}$${\displaystyle r(A)\leq r(A\cup \{x\})\leq r(A)+1}$${\displaystyle A\subseteq B\subseteq E}$${\displaystyle r(A)\leq r(B)\leq r(E)}$

คุณสมบัติเหล่านี้สามารถใช้เป็นหนึ่งในคำจำกัดความทางเลือกของแมทรอยด์จำกัดได้: ถ้าเป็นไปตามคุณสมบัติเหล่านี้ เซตอิสระของแมทรอยด์บนสามารถกำหนดได้ว่าเป็นเซตย่อยของที่มีในภาษาของเซตที่มีลำดับบางส่วนโครงสร้างแมทรอยด์ดังกล่าวเทียบเท่ากับแลตทิซทางเรขาคณิตซึ่งองค์ประกอบเป็นเซตย่อย ที่มีลำดับบางส่วนโดยการรวม ${\displaystyle (E,r)}$${\displaystyle E}$${\displaystyle A}$${\displaystyle E}$${\displaystyle r(A)=|A|}$${\displaystyle A\subset M}$

ผลต่างนี้เรียกว่าค่าศูนย์ของเซตย่อยมันคือจำนวนสมาชิกขั้นต่ำที่ต้องถูกลบออกจากเซตย่อย เพื่อให้ได้เซตอิสระ ค่าศูนย์ของเซตย่อยในเซตย่อยเรียกว่า ค่าศูนย์ ของเซตย่อย บางครั้ง ผลต่างนี้เรียกว่าอันดับร่วมของเซตย่อย ${\displaystyle |A|-r(A)}$${\displaystyle A}$${\displaystyle A}$${\displaystyle E}$${\displaystyle M}$${\displaystyle M}$${\displaystyle r(E)-r(A)}$${\displaystyle A}$

ให้เป็นเมทริกซ์บนเซตจำกัดโดยมีฟังก์ชันอันดับดังที่กล่าวมาข้างต้นการปิดหรือปริภูมิแผ่ขยายของเซตย่อยของคือเซต ${\displaystyle M}$${\displaystyle E}$${\displaystyle r}$${\displaystyle \operatorname {cl} (A)}$${\displaystyle A}$${\displaystyle E}$

${\displaystyle \operatorname {cl} (A)={\Bigl \{}\ x\in E\mid r(A)=r{\bigl (}A\cup \{x\}{\bigr )}{\Bigr \}}}$.

นี่เป็นการกำหนดตัวดำเนินการปิด โดยที่แทนเซตกำลังซึ่งมีคุณสมบัติดังต่อไปนี้: ${\displaystyle \operatorname {cl} :{\mathcal {P}}(E)\mapsto {\mathcal {P}}(E)}$${\displaystyle {\mathcal {P}}}$

• (C1) สำหรับเซตย่อยทั้งหมดของ${\displaystyle X}$${\displaystyle E}$${\displaystyle X\subseteq \operatorname {cl} (X).}$

• (C2) สำหรับเซตย่อยทั้งหมดของ${\displaystyle X}$${\displaystyle E}$${\displaystyle \operatorname {cl} (X)=\operatorname {cl} \left(\operatorname {cl} \left(X\right)\right).}$

• (C3) สำหรับเซตย่อยทั้งหมด ของ และที่มี,${\displaystyle X}$${\displaystyle Y}$${\displaystyle E}$${\displaystyle X\subseteq Y}$${\displaystyle \operatorname {cl} (X)\subseteq \operatorname {cl} (Y).}$

• (C4) สำหรับองค์ประกอบทั้งหมดและจากและเซตย่อยทั้งหมดของถ้าแล้ว${\displaystyle a}$${\displaystyle b}$${\displaystyle E}$${\displaystyle Y}$${\displaystyle E}$${\displaystyle a\in \operatorname {cl} (Y\cup \{b\})\smallsetminus \operatorname {cl} (Y)}$${\displaystyle b\in \operatorname {cl} (Y\cup \{a\})\smallsetminus \operatorname {cl} (Y).}$

คุณสมบัติสามประการแรกเหล่านี้เป็นคุณสมบัติที่กำหนดของตัวดำเนินการปิด คุณสมบัติที่สี่บางครั้งเรียกว่าคุณสมบัติการแลกเปลี่ยนMac Lane – Steinitzคุณสมบัติเหล่านี้อาจถือเป็นคำจำกัดความอื่นของ matroid: ทุกฟังก์ชันที่ปฏิบัติตามคุณสมบัติเหล่านี้จะกำหนด matroid ^{[ 4 ]}${\displaystyle \operatorname {cl} :{\mathcal {P}}(E)\to {\mathcal {P}}(E)}$

เซตที่มีการปิดเท่ากับตัวมันเองเรียกว่าเซตปิดหรือระนาบหรือปริภูมิย่อยของแมทรอยด์^{[ 5 ]}เซตปิดก็ต่อเมื่อเป็น เซต สูงสุดสำหรับอันดับของมัน หมายความว่าการเพิ่มองค์ประกอบอื่นใดลงในเซตจะทำให้อันดับเพิ่มขึ้น เซตปิดของแมทรอยด์มีลักษณะเฉพาะด้วยคุณสมบัติการแบ่งส่วนที่ครอบคลุม:

• (F1) เซตจุดทั้งหมดเป็นเซตปิด${\displaystyle E}$

• (F2) ถ้าและเป็นแฟลต แล้ว ก็เป็นแฟลตเช่นกัน${\displaystyle S}$${\displaystyle T}$${\displaystyle S\cap T}$

• (F3) ถ้าเป็นแฟลตแล้ว แต่ละองค์ประกอบของจะอยู่ในแฟลตที่ครอบคลุม เพียงแฟลตเดียวเท่านั้น (หมายความว่าครอบคลุม อย่างถูกต้องแต่ไม่มีแฟลตระหว่างและ)${\displaystyle S}$${\displaystyle E\smallsetminus S}$${\displaystyle T}$${\displaystyle S}$${\displaystyle T}$${\displaystyle S}$${\displaystyle U}$${\displaystyle S}$${\displaystyle T}$

กลุ่มของระนาบทั้งหมด ซึ่งเรียงลำดับบางส่วนโดยการรวมเซต ก่อให้เกิดแลตทิซของแมทรอยด์ในทางกลับกัน แลตทิซของแมทรอยด์ทุกอันจะก่อให้เกิดแมทรอยด์เหนือเซตของอะตอมภายใต้ตัวดำเนินการปิดต่อไปนี้: สำหรับเซตของอะตอมที่มีการเชื่อมต่อ ${\displaystyle {\mathcal {L}}(M)}$${\displaystyle L}$${\displaystyle E}$${\displaystyle S}$${\displaystyle \bigvee S}$

${\displaystyle \operatorname {cl} (S)=\{x\in E\mid x\leq \bigvee S\}.}$

ระนาบของเมทริกซ์นี้สอดคล้องกันแบบหนึ่งต่อหนึ่งกับองค์ประกอบของแลตทิซ โดยระนาบที่สอดคล้องกับองค์ประกอบของแลตทิซคือเซต ${\displaystyle y}$

${\displaystyle \{x\in E\mid x\leq y\}.}$

ดังนั้น โครงข่ายระนาบของเมทริกซ์นี้จึงสมมาตรกับเมทริกซ์ดังกล่าวโดยธรรมชาติ ${\displaystyle L}$

ใน matroid ที่มีอันดับระนาบที่มีอันดับเรียกว่าhyperplaneหรือco-atomsหรือcopointsสิ่งเหล่านี้คือระนาบที่เหมาะสมที่สุด นั่นคือ เซตย่อยเดียวของ hyperplane ที่เป็นระนาบด้วยคือเซตขององค์ประกอบทั้งหมดของ matroid นิยามที่เทียบเท่ากันคือ coatom เป็นเซตย่อยของEที่ไม่ครอบคลุมMแต่การเพิ่มองค์ประกอบอื่นใดเข้าไปจะทำให้เป็นเซตที่ครอบคลุม^{[ 6 ]}${\displaystyle r}$${\displaystyle r-1}$${\displaystyle E}$

ตระกูลของไฮเปอร์เพลนของแมทรอยด์มีคุณสมบัติดังต่อไปนี้ ซึ่งอาจถือได้ว่าเป็นสัจพจน์อีกประการหนึ่งของแมทรอยด์: ^{[ 6 ]}${\displaystyle {\mathcal {H}}}$

• (H1) เซตพื้นฐานนั้นไม่ใช่ไฮเปอร์เพลน${\displaystyle E}$

• (H2) ไม่มีเซตที่แตกต่างกันและในนั่นคือ ไฮเปอร์เพลนก่อตัวเป็นตระกูลสเปอร์เนอร์${\displaystyle X}$${\displaystyle Y}$${\displaystyle {\mathcal {H}}}$${\displaystyle X\subseteq Y}$

• (H3) สำหรับทุกค่าและ ที่แตกต่างกันจะมีค่าอยู่ด้วย${\displaystyle x\in E}$${\displaystyle Y,Z\in {\mathcal {H}}}$${\displaystyle x\notin Y\cup Z}$${\displaystyle X\in {\mathcal {H}}}$${\displaystyle (Y\cap Z)\cup \{x\}\subseteq X}$

มินตี (1966) นิยามกราฟอยด์ว่าเป็นสามสิ่งโดยที่และเป็นกลุ่มของเซตย่อยที่ไม่ว่างของซึ่งเป็นไปตามเงื่อนไขที่ว่า ${\displaystyle (L,C,D)}$${\displaystyle C}$${\displaystyle D}$${\displaystyle L}$

• (G1) ไม่มีองค์ประกอบใด(เรียกว่า "วงจร") ที่มีองค์ประกอบอื่นอยู่ภายใน${\displaystyle C}$

• (G2) ไม่มีองค์ประกอบใด(เรียกว่า "วงจรร่วม") ที่มีองค์ประกอบอื่นอยู่ภายใน${\displaystyle D}$

• (G3) ไม่มีเซตในและเซตในตัดกันที่องค์ประกอบเดียวพอดี และ${\displaystyle C}$${\displaystyle D}$

• (G4) เมื่อใดก็ตามที่แสดงเป็นผลรวมที่ไม่ซ้ำกันของเซตย่อยที่มี( เซตที่มีสมาชิกเดียว ) แล้วจะมีสมาชิกอยู่ตัวหนึ่งที่ทำให้หรือจะมีสมาชิกอยู่ตัวหนึ่งที่ทำให้${\displaystyle L}$${\displaystyle R,G,B}$${\displaystyle G=\{g\}}$${\displaystyle X\in C}$${\displaystyle g\in X\subseteq R\cup G}$${\displaystyle Y\in D}$${\displaystyle g\in Y\subseteq B\cup G}$

เขาพิสูจน์แล้วว่ามีแมทรอยด์ซึ่งเป็นคลาสของวงจร และเป็นคลาสของโควงจร ในทางกลับกัน ถ้าและเป็นคลาสของวงจรและโควงจรของแมทรอยด์ที่มีเซตพื้นฐานแล้วจะเป็นกราฟอยด์ ดังนั้น กราฟอยด์จึงให้สัจพจน์คริปโตมอร์ฟิกแบบทวิภาคของแมทรอยด์ ${\displaystyle C}$${\displaystyle D}$${\displaystyle C}$${\displaystyle D}$${\displaystyle M}$${\displaystyle E}$${\displaystyle (E,C,D)}$

ให้เป็นเซตจำกัด เซตของเซตย่อยทั้งหมดของกำหนดเซตอิสระของแมทรอยด์ เรียกว่า แมทรอย ด์ อิสระเหนือ${\displaystyle E}$${\displaystyle E}$${\displaystyle E}$

ให้เป็นเซตจำกัด และเป็นจำนวนธรรมชาติเราสามารถกำหนดมาทรอยด์บน ได้โดยการเลือกใช้เซตย่อยของสมาชิก ทุกตัวใน เป็นฐาน มาทรอยด์นี้เรียกว่ามาทรอยด์เอกรูปที่มีอันดับ มาทรอยด์เอกรูปที่มีอันดับและมีสมาชิก จะเขียนแทน ด้วย มาทรอยด์เอกรูปทั้งหมดที่มีอันดับอย่างน้อย 2 เป็นมาทรอยด์เชิงเดี่ยว (ดู§ คำศัพท์เพิ่มเติม ) มาทรอยด์เอกรูปที่มีอันดับ 2 บนจุด เรียกว่าเส้นจุดมาทรอยด์เป็นมาทรอยด์เอกรูปก็ต่อเมื่อไม่มีวงจรที่มีขนาดเล็กกว่าหนึ่งบวกกับอันดับของมาทรอยด์ ผลรวมโดยตรงของมาทรอยด์เอกรูปเรียกว่า มาทรอย ด์ แบ่งส่วน${\displaystyle E}$${\displaystyle k}$${\displaystyle E}$${\displaystyle k}$${\displaystyle E}$${\displaystyle k}$${\displaystyle k}$${\displaystyle n}$${\displaystyle U_{k,n}}$${\displaystyle n}$${\displaystyle n}$ 

ในแมทรอยด์แบบเอกรูป (uniform matroid ) ทุกองค์ประกอบเป็นลูป (องค์ประกอบที่ไม่เป็นสมาชิกของเซตอิสระใดๆ) และในแมทรอยด์แบบเอกรูปอีกแบบ (uniform matroid ) ทุกองค์ประกอบเป็นโคลูป (องค์ประกอบที่เป็นสมาชิกของทุกฐาน) ผลรวมโดยตรงของแมทรอยด์ทั้งสองประเภทนี้คือแมทรอยด์แบบแบ่งส่วน (partition matroid) ซึ่งทุกองค์ประกอบเป็นลูปหรือโคลูป เรียกว่าแมทรอยด์แบบไม่ต่อเนื่อง (discrete matroid ) นิยามที่เทียบเท่ากันของแมทรอยด์แบบไม่ต่อเนื่องคือแมทรอยด์ซึ่งเซตย่อยที่แท้จริงและไม่ว่างเปล่าทุกเซตของเซตพื้นฐานเป็นตัวแยก (separator) ${\displaystyle U_{0,n}}$${\displaystyle U_{n,n}}$${\displaystyle E}$

ทฤษฎีแมทรอยด์พัฒนาขึ้นจากการศึกษาคุณสมบัติของความเป็นอิสระและมิติในปริภูมิเวกเตอร์อย่างละเอียด มีสองวิธีในการนำเสนอแมทรอยด์ที่นิยามไว้ในลักษณะนี้:

ถ้าเป็นเซตย่อยจำกัดใดๆ ของปริภูมิเวกเตอร์เราสามารถกำหนดเมทริกซ์บน ได้โดยการ เลือกเซตอิสระของให้เป็น เซตย่อย อิสระเชิงเส้นของ${\displaystyle E}$${\displaystyle V}$${\displaystyle M}$${\displaystyle E}$${\displaystyle M}$${\displaystyle E}$

ความถูกต้องของสัจพจน์เซตอิสระสำหรับแมทรอยด์นี้เป็นผลมาจากทฤษฎีบทการแลกเปลี่ยนของสไตน์นิทซ์

ถ้า เป็นเมทรอยด์ที่สามารถนิยามได้ในลักษณะนี้ เราจะกล่าว ว่าเซตแทน${\displaystyle M}$${\displaystyle E}$${\displaystyle M}$

แมทรอยด์ประเภทนี้เรียกว่าเวกเตอร์แมทรอยด์

ตัวอย่างสำคัญของแมทรอยด์ที่กำหนดในลักษณะนี้คือ แมทรอยด์ฟาโน ซึ่งเป็นแมทรอยด์อันดับสามที่ได้มาจากระนาบฟาโนซึ่งเป็นเรขาคณิตจำกัด ที่มีเจ็ดจุด (องค์ประกอบเจ็ดอย่างของแมทรอย ด์ ) และเจ็ดเส้น (ระนาบที่ไม่ใช่ศูนย์ที่แท้จริงของแมทรอยด์) มันเป็นแมทรอยด์เชิงเส้นที่มีองค์ประกอบที่สามารถอธิบายได้ว่าเป็นจุดที่ไม่ใช่ศูนย์เจ็ดจุดในปริภูมิเวกเตอร์สามมิติเหนือฟิลด์จำกัด GF(2) อย่างไรก็ตาม ไม่สามารถแสดงแทนแมทรอยด์ฟาโนในลักษณะเดียวกันโดยใช้จำนวนจริงแทน GF(2) ได้

เมทริกซ์ ที่มีสมาชิกในฟิลด์ หนึ่งๆ จะก่อให้เกิดแมทรอยด์บนเซตของคอลัมน์ในเมทริกซ์นั้น เซตของคอลัมน์ที่ขึ้นอยู่กันในแมทรอยด์ คือเซตของคอลัมน์ที่ขึ้นอยู่กันเชิงเส้นในฐานะเวกเตอร์ ${\displaystyle A}$${\displaystyle M}$

แมท รอยด์นี้เรียกว่าแมทรอยด์คอลัมน์ของและกล่าวกันว่าแทน${\displaystyle A}$${\displaystyle A}$${\displaystyle M}$

ตัวอย่างเช่น เมทริกซ์ Fano สามารถแสดงได้ในลักษณะนี้เป็นเมทริกซ์ 3 × 7 (0,1)เมทริกซ์คอลัมน์ก็คือเมทริกซ์เวกเตอร์ภายใต้ชื่ออื่น แต่โดยทั่วไปมักมีเหตุผลที่นิยมใช้การแสดงในรูปแบบเมทริกซ์มากกว่า^{[ b ]}

แมทรอยด์ที่เทียบเท่ากับเวกเตอร์แมทรอยด์ แม้ว่าจะแสดงในรูปแบบที่แตกต่างกัน ก็เรียกว่า แมทรอยด์ ที่สามารถแสดงแทนได้หรือแมทรอยด์เชิงเส้นถ้าแมทรอยด์ที่เทียบเท่ากับเวกเตอร์แมทรอยด์เหนือฟิลด์เราจะกล่าวว่าแม ทรอยด์นั้น สามารถแสดง แทนได้เหนือฟิลด์ นั้น โดยเฉพาะอย่างยิ่ง แม ทรอยด์ ที่สามารถแสดงแทนได้ด้วยจำนวนจริงถ้ามันสามารถแสดงแทนได้เหนือจำนวนจริง ตัวอย่างเช่น แม้ว่ากราฟิกแมทรอยด์ (ดูด้านล่าง) จะแสดงในรูปของกราฟ แต่ก็สามารถแสดงแทนได้ด้วยเวกเตอร์เหนือฟิลด์ใดๆ ก็ได้ ${\displaystyle M}$${\displaystyle F}$${\displaystyle M}$${\displaystyle F}$${\displaystyle M}$

ปัญหาพื้นฐานในทฤษฎีแมทรอยด์คือการจำแนกลักษณะของแมทรอยด์ที่อาจแสดงได้เหนือฟิลด์ที่กำหนดสมมติฐานของโรตาอธิบายถึงการจำแนกลักษณะที่เป็นไปได้สำหรับทุกฟิลด์จำกัดผลลัพธ์หลักจนถึงปัจจุบันคือการจำแนกลักษณะของแมทรอยด์ไบนารี (ที่สามารถแสดงได้เหนือ GF(2)) โดยTutte (ทศวรรษ 1950) ของแมทรอยด์ไตรนารี (ที่สามารถแสดงได้เหนือฟิลด์ 3 องค์ประกอบ) โดย Reid และ Bixby และแยกต่างหากโดยSeymour (ทศวรรษ 1970) และของแมทรอยด์ควอเทอร์นารี (ที่สามารถแสดงได้เหนือฟิลด์ 4 องค์ประกอบ) โดยGeelen, Gerards และ Kapoor (2000)มีการประกาศการพิสูจน์สมมติฐานของโรตา แต่ไม่ได้ตีพิมพ์ในปี 2014 โดย Geelen, Gerards และ Whittle ^{[ 7 ]}${\displaystyle F;}$

แมทรอยด์ปกติคือ แมทรอยด์ที่สามารถแทนค่าได้ด้วยฟิลด์ที่เป็นไปได้ทั้งหมด ส่วนแมทรอยด์ Vámosเป็นตัวอย่างที่ง่ายที่สุดของแมทรอยด์ที่ไม่สามารถแทนค่าได้ด้วยฟิลด์ใดๆ เลย

แหล่งที่มาดั้งเดิมแหล่งที่สองของทฤษฎีเมทริกซ์คือทฤษฎีกราฟ

กราฟจำกัดทุกกราฟ (หรือมัลติกราฟ ) ก่อให้เกิดแมทรอยด์ดังต่อไปนี้: กำหนดให้เป็นเซตของขอบทั้งหมดในและพิจารณาเซตของขอบที่เป็นอิสระก็ต่อเมื่อเป็นป่านั่นคือ ถ้ามันไม่มีวัฏจักรแบบง่ายจากนั้นเรียกว่าแมทรอยด์วัฏจักรแมทรอยด์ที่ได้มาในลักษณะนี้เป็นแมทรอยด์กราฟิกไม่ใช่ทุกแมทรอยด์จะเป็นกราฟิก แต่แมทรอยด์ทั้งหมดที่มีสามองค์ประกอบเป็นกราฟิก^{[ 8 ]}แมทรอยด์กราฟิกทุกตัวเป็นแบบปกติ ${\displaystyle G}$${\displaystyle M(G)}$${\displaystyle E}$${\displaystyle G}$${\displaystyle M(G)}$

ต่อมาได้มีการค้นพบเมทริกซ์ชนิดอื่นๆ บนกราฟ:

• เมทริกซ์ไบเซอร์คูลาร์ของกราฟถูกกำหนดโดยการเรียกเซตของขอบว่าเป็นอิสระ หากเซตย่อยที่เชื่อมต่อกันทุกเซตมีวงจรไม่เกินหนึ่งวง กล่าวคือ เซตของขอบจะเป็นอิสระก็ต่อเมื่อเป็นซูโดฟอเรสต์

• ในกราฟแบบมีทิศทางหรือไม่มีทิศทางใดๆให้และเป็นเซตของจุดยอดที่แตกต่างกันสองเซต ในเซตให้กำหนดเซตย่อยเป็นอิสระหากมีเส้นทางที่ไม่มีจุดยอดร่วมกันจากไปยังซึ่งกำหนดเมทริกซ์บนที่เรียกว่าgammoid : ^{[ 9 ]} gammoid ที่เข้มงวดคือ gammoid ที่เซตเป็นเซตจุดยอดทั้งหมดของ^{[ 10 ]}${\displaystyle G}$${\displaystyle E}$${\displaystyle F}$${\displaystyle E}$${\displaystyle U}$${\displaystyle |U|}$${\displaystyle F}$${\displaystyle U}$${\displaystyle E}$${\displaystyle E}$${\displaystyle G}$

• ในกราฟสองส่วน สามารถสร้างแมทรอยด์ได้ โดยที่องค์ประกอบเป็นจุดยอดด้านหนึ่งของการแบ่งสองส่วน และเซตย่อยอิสระเป็นเซตของจุดปลายของการจับคู่ของกราฟ สิ่งนี้เรียกว่าแมทรอยด์แบบทรานส์เวอร์ซัล [ 11 ] [ 12 ] และเป็นกรณีพิเศษของแกมมอยด์ [ 9 ] แมทรอยด์แบบทรานส์^{เวอร์ซัลเป็นแม}ท^{รอยด์คู่} ของแกมมอยด์แบบ^{เข้มงวด[ 10 ]}${\displaystyle G=(U,V,E)}$${\displaystyle U}$

• แมทรอยด์กราฟิกได้รับการขยายความไปสู่แมทรอยด์จากกราฟแบบมี เครื่องหมาย กราฟแบบได้กำไรและกราฟแบบมีอคติ กราฟที่มีวัฏจักรเชิงเส้นที่โดดเด่นซึ่งเรียกว่า "กราฟแบบมีอคติ" จะมีแมทรอยด์สองตัว ได้แก่แมทรอยด์เฟรมและแมทรอยด์ยกของกราฟแบบมีอคติ${\displaystyle G}$${\displaystyle {\mathcal {B}}}$${\displaystyle (G,{\mathcal {B}})}$

ถ้าวัฏจักรทุกวงเป็นของกลุ่มที่โดดเด่น เมทริกซ์เหล่านี้จะตรงกับเมทริกซ์วัฏจักรของหากไม่มีวัฏจักรใดที่โดดเด่น เมทริกซ์เฟรมจะเป็นเมทริกซ์ไบเซอร์คูลา ร์ของ กราฟที่มีเครื่องหมาย ซึ่งขอบถูกกำกับด้วยเครื่องหมาย และกราฟกำไร ซึ่งเป็นกราฟที่ขอบถูกกำกับด้วยทิศทางจากกลุ่ม แต่ละกราฟจะก่อให้เกิดกราฟที่มีอคติ และดังนั้นจึงมีเมทริกซ์เฟรมและเมทริกซ์ยก${\displaystyle G}$${\displaystyle G}$

• กราฟลามานเป็นฐานของเมทริกซ์ความแข็งแกร่ง สองมิติ ซึ่ง เป็นเมทริกซ์ที่นิยามไว้ในทฤษฎีความแข็งแกร่งของโครงสร้าง

• ให้ G เป็นกราฟเชื่อมต่อ และS เป็นเซตของขอบ ให้ n เป็นเซตย่อยของ G โดยที่ G ยังคงเป็นกราฟเชื่อมต่ออยู่ ดังนั้น n ซึ่งมีเซตสมาชิกเป็น S และ n เป็นคลาสของเซตอิสระ n จะเป็นเมทริกซ์ที่เรียกว่าเมทริกซ์พันธะของG${\displaystyle G}$${\displaystyle E}$${\displaystyle I}$${\displaystyle F}$${\displaystyle E}$${\displaystyle G-F}$${\displaystyle M^{*}(G)}$${\displaystyle E}$${\displaystyle I}$${\displaystyle G}$

ฟังก์ชันอันดับคือจำนวนวัฏจักรของกราฟย่อยที่เหนี่ยวนำบนเซตย่อยของขอบซึ่งเท่ากับจำนวนขอบที่อยู่นอกป่าสูงสุดของกราฟย่อยนั้น และเท่ากับจำนวนวัฏจักรอิสระในกราฟย่อยนั้นด้วย${\displaystyle r(F)}$${\displaystyle F}$

แหล่งกำเนิดดั้งเดิมแหล่งที่สามของทฤษฎีเมทริกซ์คือทฤษฎี สนาม

การขยายขอบเขตของฟิลด์จะก่อให้เกิดแมทรอยด์:

สมมติว่าและเป็นฟิลด์ที่มีซึ่งบรรจุอยู่ภายในให้เป็นเซตย่อยจำกัดใดๆของ${\displaystyle F}$${\displaystyle K}$${\displaystyle K}$${\displaystyle F}$${\displaystyle E}$${\displaystyle K}$

กำหนดให้เซตย่อยของเป็นอิสระทางพีชคณิตหากฟิลด์ส่วนขยายมีดีกรีทรานสเซนเดน^ซ์เท่ากับ^[ 13 ^]${\displaystyle S}$${\displaystyle E}$${\displaystyle F(S)}$${\displaystyle |S|}$

แมทรอยด์ที่เทียบเท่ากับแมทรอยด์ประเภทนี้เรียกว่า แมทรอย ด์พีชคณิต^{[ 14 ]} ปัญหาของการกำหนดลักษณะเฉพาะของแมทรอยด์พีชคณิตนั้นยากมาก มีข้อมูลเกี่ยวกับเรื่องนี้น้อยมากแมทรอยด์ Vámosเป็นตัวอย่างของแมทรอยด์ที่ไม่ใช่พีชคณิต

มีวิธีการมาตรฐานบางอย่างในการสร้างมาทรอยด์ตัวใหม่จากมาทรอยด์ตัวเก่า

ถ้าเป็น matroid จำกัด เราสามารถกำหนดmatroidตั้งฉากหรือ คู่ขนานได้ โดยใช้เซตพื้นฐานเดียวกันและเรียกเซตนั้นว่าฐานในก็ต่อเมื่อส่วนเติมเต็มของเซตนั้นเป็นฐานในไม่ใช่เรื่องยากที่จะตรวจสอบว่า^เป็น matroid และคู่ขนานของคือ^{[ 15} ]${\displaystyle M}$${\displaystyle M^{*}}$${\displaystyle M^{*}}$${\displaystyle M}$${\displaystyle M^{*}}$${\displaystyle M^{*}}$${\displaystyle M}$

สามารถอธิบายคู่ตรงข้ามได้ดีพอๆ กันโดยใช้คำจำกัดความอื่นๆ ของ matroid ตัวอย่างเช่น:

• เซตจะเป็นอิสระในก็ต่อเมื่อเซตส่วนเติมเต็มของมันครอบคลุมเซต${\displaystyle M^{*}}$${\displaystyle M}$

• เซตจะเป็นวงจรของก็ต่อเมื่อส่วนเติมเต็มของเซตนั้นเป็นวงจรใน${\displaystyle M^{*}}$${\displaystyle M}$

• ฟังก์ชันอันดับของคู่คือ.${\displaystyle r^{*}(S)=|S|-r(M)+r\left(E\smallsetminus S\right)}$

ตามทฤษฎีบทของKuratowski เวอร์ชัน matroid คู่ขนานของ graphic matroid จะเป็น graphic matroid ก็ต่อเมื่อเป็น matroid ของกราฟระนาบในกรณีนี้ คู่ขนานของคือ matroid ของกราฟคู่ขนานของ^{[ 16} ] คู่ขนานของ vector matroid ที่สามารถแทนได้บนฟิลด์เฉพาะ^ก็สามารถแทนได้บน เช่นกันคู่ขนานของ transversal matroid เป็น strict gammoid และในทางกลับกัน ${\displaystyle M}$${\displaystyle M}$${\displaystyle M}$${\displaystyle G}$${\displaystyle F}$${\displaystyle F}$

ตัวอย่าง

เมทริกซ์วัฏจักรของกราฟคือเมทริกซ์คู่ของเมทริกซ์พันธะของกราฟนั้น

ถ้าMเป็นแมทรอยด์ที่มีเซตสมาชิกEและSเป็นเซตย่อยของEการจำกัดของMบนSซึ่งเขียนว่าM  | Sคือแมทรอยด์บนเซตSซึ่งเซตอิสระของมันคือเซตอิสระของMที่อยู่ในSวงจรของมันคือวงจรของMที่อยู่ในSและฟังก์ชันอันดับของมันคือฟังก์ชันอันดับของM ที่ จำกัด บนเซตย่อยของS

ในพีชคณิตเชิงเส้น สิ่งนี้สอดคล้องกับการจำกัดไปยังปริภูมิย่อยที่สร้างขึ้นโดยเวกเตอร์ในS หรือถ้าT = M − Sสิ่งนี้อาจเรียกว่าการลบ T เขียนว่าM \ TหรือM − Tซับแมทรอยด์ของMเป็นผลลัพธ์ของลำดับการลบอย่างแม่นยำ ลำดับไม่สำคัญ^{[ 17 ] [ 18 ]}

การดำเนินการคู่ของการจำกัดคือการหดตัว^{[ 19 ]}ถ้าTเป็นเซตย่อยของEการหดตัวของMโดยTซึ่งเขียนว่าM / Tคือ matroid บนเซตพื้นฐานE  −  Tซึ่งฟังก์ชันอันดับคือ[ ^{20 ] ใน} พีชคณิตเชิงเส้น สิ่งนี้สอดคล้องกับการมองที่ปริภูมิผลหารโดยปริภูมิเชิงเส้นที่สร้างขึ้นโดยเวกเตอร์ในTพร้อมกับภาพของเวกเตอร์ใน E  −  T${\displaystyle r'(A)=r(A\cup T)-r(T)}$

แมทรอยด์Nที่ได้มาจากMโดยลำดับของการดำเนินการจำกัดและการหดตัวเรียกว่าไมเนอร์ของM ^{[ 18 ] [ 21 ]} เรากล่าวว่าM มีN เป็นไมเนอร์ ตระกูลแมทรอยด์ที่สำคัญหลายตระกูลสามารถระบุลักษณะได้ด้วย แมทรอยด์ไมเนอร์ ขั้นต่ำที่ไม่เป็นส่วนหนึ่งของตระกูลนั้น สิ่งเหล่านี้เรียกว่าไมเนอร์ต้องห้ามหรือไมเนอร์ที่ถูกยกเว้น^{[ 22 ]}

ให้Mเป็นแมทรอยด์ที่มีเซตสมาชิกพื้นฐานEและให้Nเป็นแมทรอยด์อีกตัวหนึ่งบนเซตพื้นฐานFผลรวมโดยตรงของแมทรอยด์MและNคือแมทรอยด์ที่มีเซตพื้นฐานเป็นผลรวมที่ไม่ซ้ำกันของEและFและเซตอิสระเป็นผลรวมที่ไม่ซ้ำกันของเซตอิสระของMกับ เซตอิสระของN

การรวมกันของMและNคือเมทริกซ์ที่มีเซตพื้นฐานเป็นผลรวม (ไม่ใช่ผลรวมที่ไม่ซ้ำกัน) ของEและFและเซตอิสระของเมทริกซ์นี้คือเซตย่อยที่เป็นผลรวมของเซตอิสระในMและเซตอิสระในNโดยปกติแล้ว คำว่า "การรวม" จะใช้เมื่อE = Fแต่ข้อสมมตินั้นไม่จำเป็น หากEและFไม่ทับซ้อนกัน การรวมก็คือผลรวมโดยตรง

ให้Mเป็นเมทริกซ์ที่มีเซตของสมาชิกEเป็น พื้นฐาน

• Eอาจเรียกว่าเซตพื้นฐานของMและสมาชิกของ E อาจเรียกว่าจุดของM

• เซตย่อยของE แผ่คลุมMถ้าเซตปิดของมันคือEและเซตหนึ่งจะแผ่คลุมเซตปิดKถ้าเซตปิดของมันคือK

• ขนาดเส้นผ่านศูนย์กลางของแมทรอยด์ คือ ขนาดของวงจรที่เล็กที่สุด หรือเซตที่ขึ้นอยู่กับมัน

• องค์ประกอบที่สร้างวงจรองค์ประกอบเดี่ยวของMเรียกว่าลูปหรือกล่าวอีกนัยหนึ่ง องค์ประกอบจะเป็นลูปหากไม่ได้อยู่ในฐานใดๆ^{[ 8 ] [ 23 ]}

• องค์ประกอบที่ไม่สังกัดวงจรใด ๆ เรียกว่าโคลูปหรืออิสทมัสในทำนองเดียวกัน องค์ประกอบจะเป็นโคลูปก็ต่อเมื่อมันสังกัดทุกฐาน

ลูปและโคลูปเป็นคู่กัน^{[ 23 ]}

• ถ้าเซตสององค์ประกอบ { f, g ^}เป็นวงจรของMแล้วfและgจะขนานกันในM [ ^{8 ]}

• แมทรอยด์เรียกว่าเรียบง่ายหากไม่มีวงจรที่ประกอบด้วยองค์ประกอบ 1 หรือ 2 ตัว นั่นคือไม่มีลูปและไม่มีองค์ประกอบขนาน คำว่าเรขาคณิตเชิงการจัดเรียงก็ใช้เช่นกัน^{[ 8 ]} แมทรอยด์เรียบง่ายที่ได้จากแมทรอยด์M อีกตัวหนึ่ง โดยการลบลูปทั้งหมดและลบองค์ประกอบหนึ่งตัวออกจากวงจร 2 องค์ประกอบแต่ละวงจนกว่าจะไม่มีวงจร 2 องค์ประกอบเหลืออยู่ เรียกว่าการทำให้M ง่ายขึ้น[ 24 ^]แมทรอยด์เรียกว่าร่วมเรียบง่ายหากแมทรอยด์คู่ของมันเรียบง่าย^{[ 25 ]}

• การรวมกันของวงจรบางครั้งเรียกว่าวงจรของMดังนั้น วงจรจึงเป็นส่วนเติมเต็มของระนาบของเมทริกซ์คู่ (การใช้แบบนี้ขัดแย้งกับความหมายทั่วไปของ "วงจร" ในทฤษฎีกราฟ)

• ตัวแยกของMคือเซตย่อยSของEโดยที่. ตัวแยก ที่เหมาะสมหรือไม่สำคัญคือตัวแยกที่ไม่ใช่Eหรือเซตว่าง^{[ 26 ]}ตัวแยกที่ไม่สามารถลดทอนได้คือตัวแยกที่ไม่ว่างซึ่งไม่มีตัวแยกที่ไม่ว่างอื่นอยู่ภายใน ตัวแยกที่ไม่สามารถลดทอนได้จะแบ่งเซตพื้นฐานEออก เป็นส่วนๆ${\displaystyle r(S)+r(E-S)=r(M)}$

• แมทรอยด์ที่ไม่สามารถเขียนเป็นผลรวมโดยตรงของแมทรอยด์ที่ไม่ว่างเปล่าสองตัว หรือเทียบเท่ากับที่ไม่มีตัวคั่นที่เหมาะสม เรียกว่าเชื่อมต่อหรือไม่สามารถ แยกย่อยได้ แมทรอยด์จะเชื่อมต่อก็ต่อเมื่อคู่ของมันเชื่อมต่อ^{[ 27 ]}

• ซับแมทรอยด์ที่ไม่สามารถลดทอนได้สูงสุดของMเรียกว่าส่วนประกอบของMส่วนประกอบคือข้อจำกัดของMต่อตัวแยกที่ไม่สามารถลดทอนได้ และในทางกลับกัน ข้อจำกัดของMต่อตัวแยกที่ไม่สามารถลดทอนได้ก็คือส่วนประกอบ ตัวแยกคือการรวมกันของส่วนประกอบ^{[ 26 ]}

• แมทรอยด์Mเรียกว่าเฟรมแมทรอยด์หากแมทรอยด์นั้นหรือแมทรอยด์ที่บรรจุแมทรอยด์นั้น มีฐานที่จุดทั้งหมดของMอยู่ในเส้นที่เชื่อมคู่ขององค์ประกอบฐาน^{[ 28 ]}

• เรียกว่า matroid แบบปูพื้นหากวงจรทั้งหมดของมีขนาดอย่างน้อยเท่ากับอันดับของมัน^{[ 29 ]}

• โพลีโทปฐาน คือส่วนนูนของเวกเตอร์บ่งชี้ของฐานของ${\displaystyle P_{M}}$${\displaystyle M}$

• โพลีโทปความเป็นอิสระของคือเปลือกนูนของเวกเตอร์ตัวบ่งชี้ของเซตอิสระของ${\displaystyle M}$${\displaystyle M}$

ปัญหาการหาค่าเหมาะสมที่สุดเชิงการจัดเรียงที่สำคัญหลายอย่างสามารถแก้ไขได้อย่างมีประสิทธิภาพบนทุกเมทริกซ์ โดยเฉพาะอย่างยิ่ง:

• การค้นหาเซตอิสระที่มีน้ำหนักสูงสุดในmatroid ที่มีน้ำหนักสามารถแก้ไขได้ด้วยอัลกอริทึมแบบโลภข้อเท็จจริงนี้อาจใช้เพื่อกำหนดลักษณะของ matroid ได้ด้วยซ้ำ: หากตระกูลFของเซตที่ปิดภายใต้การเลือกเซตย่อย มีคุณสมบัติที่ว่าไม่ว่าเซตจะมีน้ำหนักอย่างไร อัลกอริทึมแบบโลภก็จะพบเซตที่มีน้ำหนักสูงสุดในตระกูล ดังนั้นFจะต้องเป็นตระกูลของเซตอิสระของ matroid ^{[ 30 ]}

• ปัญหาการแบ่งส่วนของแมทรอยด์คือการแบ่งองค์ประกอบของแมทรอยด์ออกเป็นเซตอิสระให้น้อยที่สุดเท่าที่จะเป็นไปได้ และปัญหาการบรรจุแมทรอยด์คือการหาเซตแผ่ขยายที่ไม่ซ้ำกันให้ได้มากที่สุดเท่าที่จะเป็นไปได้ ทั้งสองปัญหาสามารถแก้ไขได้ในเวลาพหุนาม และสามารถขยายไปสู่ปัญหาการคำนวณอันดับหรือการหาเซตอิสระในผลรวมของแมทรอยด์ได้

• การหาจุดตัดของเมทริกซ์รอยด์สองตัวขึ้นไปบนเซตพื้นฐานเดียวกัน คือกลุ่มของเซตที่เป็นอิสระพร้อมกันในแต่ละเมทริกซ์รอยด์ ปัญหาการหาเซตที่ใหญ่ที่สุด หรือเซตที่มีน้ำหนักสูงสุด ในจุดตัดของเมทริกซ์รอยด์สองตัว สามารถหาคำตอบได้ในเวลาพหุนามและให้คำตอบสำหรับปัญหาการหาค่าเหมาะสมที่สุดเชิงการจัดเรียงที่สำคัญอื่นๆ อีกมากมาย ตัวอย่างเช่นการจับคู่สูงสุดในกราฟสองส่วนสามารถแสดงได้ในรูปของปัญหาการหาจุดตัดของเมทริกซ์รอยด์แบ่ง ส่วนสองตัว อย่างไรก็ตาม การหาเซตที่ใหญ่ที่สุดในจุดตัดของเมทริกซ์รอยด์สามตัวขึ้นไปนั้นเป็นปัญหาNP- complete

ระบบคำนวณแบบสแตนด์อะโลนสองระบบสำหรับใช้กับแมทรอยด์ ได้แก่Oid ของ Kingan และMacek ของ Hlineny ทั้งสองเป็นซอฟต์แวร์โอเพนซอร์ส "Oid" เป็นระบบซอฟต์แวร์แบบโต้ตอบและขยายได้สำหรับการทดลองกับแมทรอยด์ "Macek" เป็นระบบซอฟต์แวร์เฉพาะทางที่มีเครื่องมือและรูทีนสำหรับการคำนวณเชิงการจัดเรียงที่มีประสิทธิภาพพอสมควรกับแมทรอยด์ที่สามารถแสดงแทนได้

ทั้งระบบซอฟต์แวร์คณิตศาสตร์โอเพนซอร์สSAGEและMacaulay2 ต่าง ก็มีแพ็กเกจ matroid Mapleมีแพ็กเกจสำหรับจัดการกับ matroid ตั้งแต่เวอร์ชัน 2024 ^{[ 31 ]}

มีพหุนามสำคัญสองตัวที่เกี่ยวข้องกับแมทรอยด์จำกัดMบนเซตพื้นฐานEแต่ละตัวเป็นแมทรอยด์ไม่เปลี่ยนแปลงซึ่งหมายความว่าแมทรอยด์ที่สมมาตรกันจะมีพหุนามเดียวกัน

พหุนามลักษณะเฉพาะของM – บางครั้งเรียกว่า^พหุนามสี [ ^{32 ]}แม้ว่าจะไม่นับการระบายสี – ถูกกำหนดให้เป็น

${\displaystyle p_{M}(\lambda ):=\sum _{S\subseteq E}(-1)^{|S|}\lambda ^{r(E)-r(S)},}$

หรือเทียบเท่า (ตราบใดที่เซตว่างปิดอยู่ในM ) ดังนี้

${\displaystyle p_{M}(\lambda ):=\sum _{A}\mu (\emptyset ,A)\lambda ^{r(E)-r(A)},}$

โดยที่ μ แทนฟังก์ชันโมเบียสของแลตทิซเรขาคณิตของแมทรอยด์ และผลรวมจะคำนวณจากระนาบ A ทั้งหมดของแมทรอยด์^{[ 33 ]}

• เมื่อMคือเมทริกซ์วัฏจักรM ( G ) ของกราฟGพหุนามลักษณะเฉพาะจะเป็นการแปลงเล็กน้อยของพหุนามสีซึ่งกำหนดโดย χG ₍  λ) = λc ^p M _{( G )}  ( λ ₎โดยที่cคือจำนวนส่วนประกอบที่เชื่อมต่อกันของG

• เมื่อMคือเมทริกซ์พันธะM *( G ) ของกราฟGพหุนามลักษณะเฉพาะจะเท่ากับ พหุ นามการไหลของG

• เมื่อMคือ matroid M ( A ) ของการจัดเรียงAของระนาบเชิงเส้นใน(หรือF ⁿโดยที่Fเป็นฟิลด์ใดๆ) พหุนามลักษณะเฉพาะของการจัดเรียงจะกำหนดโดยp _A  ( λ ) = λ ^{n − r ( M )} p _M  ( λ )${\displaystyle \mathbb {R} ^{n}}$

ค่าคงที่เบต้าของแมทรอยด์ที่Crapo (1967) แนะนำ อาจแสดงได้ในรูปของพหุนามลักษณะเฉพาะเป็นการประเมินอนุพันธ์^{[ 34 ]}${\displaystyle p}$

${\displaystyle \beta (M)=(-1)^{r(M)-1}p_{M}'(1)}$

หรือโดยตรงเป็น^{[ 35 ]}

${\displaystyle \beta (M)=(-1)^{r(M)}\sum _{X\subseteq E}(-1)^{|X|}r(X).}$

ค่าคงที่เบต้าเป็นค่าที่ไม่เป็นลบ และเป็นศูนย์ก็ต่อเมื่อไม่มีการเชื่อมต่อ หรือว่างเปล่า หรือเป็นวงรอบ มิฉะนั้นจะขึ้นอยู่กับแลตติซของระนาบของเท่านั้นถ้าไม่มีวงรอบและโควงรอบแล้ว^{[ 35 ]}${\displaystyle M}$${\displaystyle M}$${\displaystyle M}$${\displaystyle \beta (M)=\beta (M^{*})}$

จำนวน วิทนีย์ชนิดแรกคือสัมประสิทธิ์ของกำลังของในพหุนามลักษณะเฉพาะ โดยเฉพาะอย่างยิ่งจำนวนวิทนีย์ที่คือสัมประสิทธิ์ของและ คือผลรวมของค่าฟังก์ชันโมเบียส: ${\displaystyle M}$${\displaystyle \lambda }$${\displaystyle i}$${\displaystyle w_{i}(M)}$${\displaystyle \lambda ^{r(M)-i}}$

${\displaystyle w_{i}(M)=\sum \{\mu (\emptyset ,A):r(A)=i\},}$

ผลรวมของแฟลตที่มีลำดับที่ถูกต้อง ตัวเลขเหล่านี้จะสลับเครื่องหมายกัน ดังนั้นสำหรับ. ${\displaystyle (-1)^{i}w_{i}(M)>0}$${\displaystyle 0\leq i\leq r(M)}$

ตัวเลขวิทนีย์ประเภทที่สองคือจำนวนแฟลตในแต่ละลำดับชั้น กล่าวคือคือ จำนวน  แฟลต ตามลำดับชั้น${\displaystyle M}$${\displaystyle W_{i}(M)}$${\displaystyle i}$

จำนวนวิทนีย์ทั้งสองชนิดเป็นการขยายความของจำนวนสเตอร์ลิงชนิดที่หนึ่งและชนิดที่สอง ซึ่งเป็นจำนวนวิทนีย์ของมาทรอยด์วัฏจักรของกราฟสมบูรณ์และเทียบเท่ากับของแลตทิซพาร์ติชัน จำนวน เหล่านี้ได้รับการตั้งชื่อตามฮัสเลอร์ วิทนีย์ผู้ร่วมก่อตั้งทฤษฎีมาทรอยด์ โดยจิอัน-คาร์โล โรตาชื่อนี้ได้รับการขยายไปใช้กับจำนวนที่คล้ายกันสำหรับเซตที่มีลำดับบางส่วน แบบจำกัด ด้วย

พหุนาม Tutteของ matroid เป็นการขยายพหุนามลักษณะเฉพาะไปสู่ตัวแปรสองตัว ทำให้มีการตีความเชิงการจัดเรียงที่หลากหลายมากขึ้น และยังมีคุณสมบัติความเป็นคู่ด้วย ${\displaystyle T_{M}(x,y)}$

${\displaystyle T_{M^{*}}(x,y)=T_{M}(y,x),}$

ซึ่งหมายถึงความสัมพันธ์แบบทวิภาคหลายประการระหว่างคุณสมบัติของและคุณสมบัติของนิยามหนึ่งของพหุนาม Tutte คือ ${\displaystyle M}$${\displaystyle M^{*}}$

${\displaystyle T_{M}(x,y)=\sum _{S\subseteq E}(x-1)^{r(M)-r(S)}\ (y-1)^{|S|-r(S)}.}$

สิ่งนี้แสดงพหุนาม Tutte เป็นการประเมิน พหุ ^นามอันดับร่วมหรือพหุนามสร้างอันดับ [ ^{36 ]}

${\displaystyle R_{M}(u,v)=\sum _{S\subseteq E}u^{r(M)-r(S)}v^{|S|-r(S)}.}$

จากนิยามนี้ จะเห็นได้ง่ายว่าพหุนามลักษณะเฉพาะนั้น เป็นการประเมินค่าของโดยเฉพาะอย่างยิ่ง ${\displaystyle T_{M}}$

${\displaystyle p_{M}(\lambda )=(-1)^{r(M)}T_{M}(1-\lambda ,0).}$

นิยามอีกประการหนึ่งคือในแง่ของกิจกรรมภายในและภายนอก และผลรวมเหนือฐาน ซึ่งสะท้อนถึงข้อเท็จจริงที่ว่าคือจำนวนฐาน^{[ 37 ]}ซึ่งผลรวมเหนือเซตย่อยที่น้อยกว่าแต่มีเงื่อนไขที่ซับซ้อนกว่า เป็นนิยามดั้งเดิมของ Tutte ${\displaystyle T(1,1)}$

มีคำจำกัดความเพิ่มเติมในแง่ของการเรียกซ้ำโดยการลบและการหดตัว^{[ 38 ]}เอกลักษณ์การลบ-การหดตัวคือ

${\displaystyle F(M)=F(M-e)+F(M/e)}$

เมื่อไม่ใช่ทั้งลูปหรือโคลูป ค่าคงที่ของแมทรอยด์ (กล่าวคือ ฟังก์ชันที่ให้ค่าเดียวกันบนแมทรอยด์ที่สมมาตรกัน) ที่สอดคล้องกับการเรียกซ้ำนี้และเงื่อนไขการคูณ ${\displaystyle e}$

${\displaystyle F(M\oplus M')=F(M)F(M')}$

กล่าวกันว่าเป็น ตัวแปร คงที่ของ Tutte–Grothendieck ^{[ 36 ]}พหุนาม Tutte เป็นตัวแปรคงที่ทั่วไปที่สุดดังกล่าว กล่าวคือ พหุนาม Tutte เป็นตัวแปรคงที่ของ Tutte–Grothendieck และตัวแปรคงที่ดังกล่าวทุกตัวเป็นการประเมินค่าของพหุนาม Tutte ^{[ 32 ]}

พหุนามทุตเต ของกราฟ คือ พหุนามทุตเตของเมทริกซ์วัฏจักรของกราฟนั้น ${\displaystyle T_{G}}$${\displaystyle T_{M(G)}}$

ทฤษฎีของแมทรอยด์อนันต์นั้นซับซ้อนกว่าทฤษฎีของแมทรอยด์จำกัดมาก และเป็นหัวข้อเฉพาะของตัวเองมาเป็นเวลานานแล้ว หนึ่งในความยากลำบากคือ มีคำจำกัดความที่สมเหตุสมผลและมีประโยชน์มากมาย แต่ไม่มีคำจำกัดความใดที่ดูเหมือนจะครอบคลุมทุกแง่มุมที่สำคัญของทฤษฎีแมทรอยด์จำกัดได้ ตัวอย่างเช่น ดูเหมือนจะเป็นเรื่องยากที่จะรวมฐาน วงจร และความเป็นคู่ไว้ในแนวคิดเดียวของแมทรอยด์อนันต์

นิยามที่ง่ายที่สุดของแมทรอยด์อนันต์คือการกำหนดให้มีอันดับจำกัดกล่าวคือ อันดับของE มีค่า จำกัด ทฤษฎีนี้คล้ายกับทฤษฎีของแมทรอยด์จำกัด ยกเว้นความล้มเหลวของความเป็นคู่เนื่องจากความจริงที่ว่าคู่ของแมทรอยด์อนันต์ที่มีอันดับจำกัดนั้นไม่มีอันดับจำกัด แมทรอยด์ที่มีอันดับจำกัดรวมถึงเซตย่อยใด ๆ ของปริภูมิเวกเตอร์มิติจำกัดและส่วนขยายฟิลด์ที่มีระดับความเหนือ ธรรมชาติ จำกัด

การสรุปทั่วไปแบบอนันต์ที่ง่ายที่สุดถัดไปคือ แมทรอยด์จำกัด หรือที่รู้จักกันในชื่อพรีจีโอเมทรีแมทรอยด์ที่มีเซตพื้นฐานอาจเป็นอนันต์นั้นเรียกว่า แมทรอยด์จำกัดถ้ามันมีคุณสมบัติว่า

${\displaystyle x\in \operatorname {cl} (Y)\ \Leftrightarrow \ {\text{ there is a finite set }}Y'\subseteq Y{\text{ such that }}x\in \operatorname {cl} (Y').}$

ในทำนองเดียวกัน เซตที่ขึ้นอยู่กันทุกเซตจะประกอบด้วยเซตที่ขึ้นอยู่กันจำนวนจำกัด

ตัวอย่างเช่น การพึ่งพาเชิงเส้นของเซตย่อยใดๆ ใน ปริภูมิเวกเตอร์มิติอนันต์(แต่ไม่ใช่การพึ่งพาอนันต์อย่างในปริภูมิฮิลเบิร์ตและปริภูมิบานาค ) และการพึ่งพาเชิงพีชคณิตในเซตย่อยใดๆ ของส่วนขยายฟิลด์ที่มีระดับความเหนือธรรมชาติอาจเป็นอนันต์ อีกครั้งหนึ่ง คลาสของแมทรอยด์จำกัดไม่ใช่คลาสคู่ตัวเอง เพราะคลาสคู่ของแมทรอยด์จำกัดไม่ใช่คลาสจำกัด

เมทริกซ์อนันต์จำกัด (Finitary infinite matroids) ถูกศึกษาในทฤษฎีแบบจำลอง (Model Theory ) ซึ่งเป็นสาขาหนึ่งของตรรกศาสตร์ทางคณิตศาสตร์ที่มีความเชื่อมโยงอย่างแน่นหนากับพีชคณิต (Algebra )

ในช่วงปลายทศวรรษ 1960 นักทฤษฎีแมทรอยด์ได้เรียกร้องหาแนวคิดที่ครอบคลุมมากขึ้น ซึ่งมีลักษณะร่วมกันระหว่างแมทรอยด์จำกัดและขยายแนวคิดทวิภาวะของแมทรอยด์เหล่านั้น มีการกำหนดแนวคิดเกี่ยวกับแมทรอยด์อนันต์มากมายเพื่อตอบสนองต่อความท้าทายนี้ แต่คำถามยังคงเปิดอยู่ หนึ่งในแนวทางที่ DA Higgs ตรวจสอบกลายเป็นที่รู้จักในชื่อB-matroidsและได้รับการศึกษาโดย Higgs, Oxley และคนอื่นๆ ในช่วงทศวรรษ 1960 และ 1970 จากผลลัพธ์ล่าสุดของBruhn et al. (2013)พบว่าสามารถแก้ปัญหาได้ โดยพวกเขาได้มาถึงแนวคิดเดียวกันโดยอิสระ และได้เสนอระบบสัจพจน์ที่เทียบเท่ากันห้าระบบ ได้แก่ ความเป็นอิสระ ฐาน วงจร การปิด และอันดับ ทวิภาวะของ B-matroids เป็นการขยายทวิภาวะที่สามารถสังเกตได้ในกราฟอนันต์

หลักการความเป็นอิสระมีดังต่อไปนี้:

1. เซตว่างเป็นอิสระ
2. เซตย่อยทุกเซตของเซตอิสระล้วนเป็นเซตอิสระเช่นกัน
3. สำหรับ เซตอิสระที่ไม่ใช่ เซตสูงสุด (ภายใต้การรวมเซต) และเซตอิสระสูงสุด ทุกเซต จะมีเซตอิสระอยู่ เซตหนึ่ง${\displaystyle I}$${\displaystyle J}$${\displaystyle x\in J\smallsetminus I}$${\displaystyle I\cup \{x\}}$
4. สำหรับทุกเซตย่อยของปริภูมิฐาน ทุกเซตย่อยอิสระของสามารถขยายไปเป็นเซตย่อยอิสระสูงสุดของได้${\displaystyle X}$${\displaystyle I}$${\displaystyle X}$${\displaystyle X}$

ด้วยหลักการพื้นฐานเหล่านี้ เมทริกซ์ทุกตัวจึงมีเมทริกซ์คู่ขนาน

ทฤษฎี Matroid ถูกนำเสนอโดยWhitney (1935)นอกจากนี้ยังถูกค้นพบโดยอิสระโดยTakeo Nakasawaซึ่งผลงานของเขาถูกลืมเลือนไปหลายปี ( Nishimura & Kuroda (2009) )

ในบทความสำคัญของเขา Whitney ได้เสนอสัจพจน์สองข้อสำหรับความเป็นอิสระ และกำหนดโครงสร้างใดๆ ที่เป็นไปตามสัจพจน์เหล่านี้ว่าเป็น "แมทรอยด์" ^{[ c ]} ข้อสังเกตที่สำคัญของเขาคือสัจพจน์เหล่านี้ให้แนวคิดเชิงนามธรรมของ "ความเป็นอิสระ" ที่พบได้ทั่วไปในทั้งกราฟและเมทริกซ์ ด้วยเหตุนี้ คำศัพท์หลายคำที่ใช้ในทฤษฎีแมทรอยด์จึงคล้ายกับคำศัพท์สำหรับแนวคิดที่คล้ายคลึงกันในพีชคณิตเชิงเส้นหรือทฤษฎี กราฟ

หลังจากที่ Whitney เขียนเกี่ยวกับ matroid เป็นครั้งแรกได้ไม่นาน MacLane (1936)ก็ได้เขียนบทความสำคัญเกี่ยวกับความสัมพันธ์ของ matroid กับเรขาคณิตเชิงโปรเจคทีฟหนึ่งปีต่อมาvan der Waerden (1937)ก็ได้กล่าวถึงความคล้ายคลึงกันระหว่างการพึ่งพาเชิงพีชคณิตและการพึ่งพาเชิงเส้นในตำราคลาสสิกเรื่องพีชคณิตสมัยใหม่ของเขา

ในช่วงทศวรรษ 1940 ริชาร์ด ราโดได้พัฒนาทฤษฎีเพิ่มเติมภายใต้ชื่อ "ระบบความเป็นอิสระ" โดยมุ่งเน้นไปที่ทฤษฎีเชิงตัดขวางซึ่งชื่อที่เขาใช้เรียกสาขาวิชานี้ยังคงถูกนำมาใช้บ้างในปัจจุบัน

ในช่วงทศวรรษ 1950 WT Tutteกลายเป็นบุคคลสำคัญที่สุดในทฤษฎีแมทรอยด์ ซึ่งเป็นตำแหน่งที่เขารักษาไว้ได้เป็นเวลาหลายปี ผลงานของเขามีมากมาย รวมถึง

• การกำหนดลักษณะของเมทริกซ์ไบนารี เมทริกซ์ปกติและ เมทริก ซ์กราฟิกโดยใช้ไมเนอร์ที่ถูกยกเว้น

• ทฤษฎีบทการแทนเมทริกซ์ปกติ

• ทฤษฎีกลุ่มลูกโซ่และเมทริกซ์ของกลุ่มเหล่านั้น

และเครื่องมือที่เขาใช้เพื่อพิสูจน์ผลลัพธ์หลายอย่างของเขา:

• ทฤษฎีบทเส้นทาง

• " ทฤษฎีบทตุตเตโฮโมโทพี " (ดู เช่นTutte (1965) )

ซึ่งมีความซับซ้อนมากจนนักทฤษฎีรุ่นหลังต้องพยายามอย่างมากเพื่อขจัดความจำเป็นในการใช้สิ่งเหล่านี้ในการพิสูจน์^{[ d ]}

Crapo (1969)และBrylawski (1972)ได้ขยายแนวคิด "ไดโครเมต" ของ Tutte ซึ่งเป็นพหุนามกราฟิกที่รู้จักกันในชื่อพหุนาม Tutte (ตั้งชื่อโดย Crapo) ไปสู่เมทริกซ์ งานวิจัยของพวกเขาได้รับการต่อยอดด้วยบทความจำนวนมากในช่วงไม่นานมานี้ (โดยเฉพาะในช่วงทศวรรษ 2000) แม้ว่าจะไม่มากเท่ากับงานวิจัยเกี่ยวกับพหุนาม Tutte ของกราฟก็ตาม

ในปี 1976 โดมินิก เวลช์ได้ตีพิมพ์หนังสือเล่มแรกที่ครอบคลุมเกี่ยวกับทฤษฎีเมทริกซ์

ทฤษฎีบทการแยกส่วนของPaul Seymour สำหรับ matroid ปกติ ( Seymour (1980) ) เป็นผลงานที่สำคัญและมีอิทธิพลมากที่สุดในช่วงปลายทศวรรษ 1970 และทศวรรษ 1980 อีกหนึ่งผลงานสำคัญโดยKahn & Kung (1982)แสดงให้เห็นว่าเหตุใดเรขาคณิตเชิงโปรเจคทีฟและเรขาคณิตของ Dowlingจึงมีบทบาทสำคัญในทฤษฎี matroid

ในช่วงทศวรรษ 1980 มีผู้มีส่วนร่วมสำคัญอื่นๆ อีกมากมาย แต่เราไม่ควรละเลยที่จะกล่าวถึงการขยายแนวคิดของGeoff Whittle เกี่ยวกับเมทริกซ์ไบนารีที่สามารถแทนได้ด้วยจำนวนตรรกยะไปยังเมทริกซ์ไตรภาค ( Whittle 1995 ) ซึ่งอาจเป็นผลงานชิ้นเอกที่สำคัญที่สุดในช่วงทศวรรษ 1990

ในช่วงเวลาปัจจุบัน (ตั้งแต่ประมาณปี 2000) โครงการ Matroid Minors ของGeelen , Gerards, Whittle และคนอื่นๆ^{[ e ]} ได้สร้างความก้าวหน้าอย่างมากในทฤษฎีโครงสร้างของ matroid นอกจากนี้ยังมีบุคคลอื่นๆ อีกมากมายที่ได้มีส่วนร่วมในทฤษฎี matroid ส่วนนี้ ซึ่ง (ในช่วงทศวรรษแรกและทศวรรษที่สองของศตวรรษที่ 21) กำลังเฟื่องฟู

นักคณิตศาสตร์ผู้บุกเบิกการศึกษาเกี่ยวกับแมทรอยด์ ได้แก่

ผู้สนับสนุนหลักรายอื่นๆ ได้แก่

• แอนติแมทรอยด์  – ระบบทางคณิตศาสตร์ของการเรียงลำดับหรือเซตที่มีสัจพจน์การแลกเปลี่ยนแบบแอนติ
• แมทรอยด์ค็อกซ์เตอร์  – การวางนัยทั่วไปของแมทรอยด์ในเชิงทฤษฎีกลุ่ม
• Greedoid  – ระบบเซตที่ใช้ในการหาค่าเหมาะสมที่สุดแบบโลภ (greedy optimization)
• เมทริกซ์เชิงทิศทาง  – นามธรรมของพีชคณิตเชิงเส้นแบบมีลำดับ
• โพลีแมทรอยด์  – รูปแบบมัลติเซตที่เทียบเท่ากับแมทรอยด์
• พรีจีโอเมทรี (ทฤษฎีแบบจำลอง)  – การกำหนดสูตรของแมทริกซ์โดยใช้ตัวดำเนินการปิด
• เดลต้าแมทรอยด์ – การวางนัยทั่วไปด้วยรูปแบบสมมาตรของสัจพจน์การแลกเปลี่ยนฐาน

• "Matroid" . สารานุกรมคณิตศาสตร์ . EMS Press . 2001 [1994].

• คิงแกน, แซนดรา. "ทฤษฎีมาทรอยด์" . userhome.brooklyn.cuny.edu (เว็บไซต์ส่วนตัวทางวิชาการ). วิทยาลัยบรูคลิน . บรูคลิน, นิวยอร์ก: มหาวิทยาลัยซิตี้แห่งนิวยอร์ก .— บรรณานุกรมขนาดใหญ่ที่รวบรวมบทความเกี่ยวกับ Matroid, ซอฟต์แวร์ Matroid และลิงก์ต่างๆ

• Locke, SC "อัลกอริทึมที่โลภ" math.fau.edu (เว็บไซต์ส่วนตัวทางวิชาการ) โบคา ราตัน, ฟลอริดา: มหาวิทยาลัยฟลอริดาแอตแลนติก

• Pagano, Steven R. "Matroids and signed graphs" . math.binghamton.edu (เว็บไซต์ส่วนตัวทางวิชาการ). บิงแฮมตัน, นิวยอร์ก: มหาวิทยาลัยบิงแฮมตัน .

• Hubenthal, Mark. "ภาพรวมโดยย่อของเมทริกซ์" (PDF) math.washington.edu (เว็บไซต์ส่วนตัวทางวิชาการ) . ซีแอตเติล, วอชิงตัน: ​​มหาวิทยาลัยวอชิงตัน . เก็บถาวรจากต้นฉบับ(PDF)เมื่อวันที่ 12 สิงหาคม 2553— ให้หลักฐานพิสูจน์สำหรับข้อความในบทความนี้

• อ็อกซ์ลีย์, เจมส์. "แมทรอยด์คืออะไร?" (PDF) . math.lsu.edu (เว็บไซต์ส่วนตัวทางวิชาการ). แบตันรูจ, รัฐลุยเซียนา: มหาวิทยาลัยรัฐลุยเซียนา .

• White, Neil, ed. (1992b). Matroid Applications . Cambridge University Press. ISBN 978-0-5213-8165-9ISSN 0953-4806 – ผ่าน  ทาง Google Books