Mátrix

Legyen S és O két véges halmaz. Az S x O Descartes-szorzaton értelmezett függvényeket mátrixnak nevezzük.

Ez az absztrakt definíció első látásra szokatlan lehet, de aki azonosítja ezt a fogalmaz a megszokott mátrix fogalommal az láthatja természetességét.

Egy véges Descartes-szorzaton értelmezett f függvény megadása egy táblázattal történhet. S elemeit soroknak és O elemeit oszlopoknak hívjuk. S és O elemeit is felsorolhatjuk S={s1,s2,...,sn}, O={o1,o2,...,on}. A függvény megadása történhet az S x O értelmezési nm darab elemén felvett nm érték megadásával, amely lerajzolására egy n sort és m oszlopot tartalmazó táblázat a legalkalmasabb: f(si,oj) a táblázat i-edik sorának és j-edik oszlopának találkozásában szerepel.

A fenti absztrakt definícióban nem tettünk fel semmit a függvény értékkészletéről, azaz mátrixunk elemeiről. Ezek általában számok, de lehetnek polinomok, halmazok, gyümölcsök, betűk és más objektunok is.

Végeredményben remélhetőleg eljutottunk oda, hogy egy mátrix semmi más csak egy táblázat.

Persze a fenti tárgyalást általában megfordítjuk. Egy táblázatból indulunk ki és azt mondjuk a sorok az S halmaz elemeivel azonosítottak, míg az oszlopok az O halmaz elemeivel.

Példa: Egy lineáris egyenletrendszer mátrixa. Egy lineáris egyenletrendszernél szerepel egy O ismeretlen-halmaz (ezeket álatalában betűkkel jelölik és változóknak vagy ismeretleneknek nevezik) és egy S összefüggés-halmaz (esetünkben ezek lineáris egyenletek). Egy nyilvánvaló függvényt írhatunk fel: Egy s összefüggéshez és egy o ismeretlenhez, hozzárendelhetjük o együtthatóját az s összefüggésben (e(s,o)-t). Ezzel egy mátrixot definiáltunk. Általában O és S elemei is rendezettek (van egy első, második, ... ismeretlenünk és hasonlóan első, második,... egyenletünk). Ekkor az e(s,o) együttható helyett ei,j-t írhatunk, ha s az i-edik egyenlet és o a j-edik ismeretlen.

Példa: Egy egyszerű gráf szomszédsági mátrixa. Egy egyszerű gráf azonosítható egy szomszédsági relációval V-n, a csúcshalmazon. A szomszédsági reláció V x V egy R részhalmaza, ami azonosítható karakterisztikus függvényével, azaz azzal V x V -> {0,1} függvénnyel, amely egy (u,v) párhoz akkor és csak akkor rendel 1-et ha (u,v) R egy eleme, azaz relációban állnak egymással.