Combinatorial minors for matrix functions and their applications

• Autorzy: Shevelev V.

Warianty tytułu

PL

Minory kombinatoryczne dla funkcji macierzowych i ich zastosowania

• Języki publikacji: EN

Abstrakty

EN

As well known, permanent of a square (0,1)-matrix A of order n enumerates the permutations β of 1, 2, ..., n with the incidence matrices B ≤ A. To obtain enumerative information on even and odd permutations with condition B ≤ A, we should calculate two-fold vector (ɑ1, ɑ2) with ɑ1 + ɑ2 = per A. More general, the introduced ω-permanent, where ω = e2πi/m, we calculate as m-fold vector. For these and other matrix functions we generalize the Laplace theorem of their expansion over elements of the first row, using the defined so-called “combinatorial minors”. In particular, in this way, we calculate the cycle index of permutations with condition B ≤ A.

PL

Jak wiadomo, permanent (0, 1)-macierzy kwadratowej A stopnia n podaje liczbę permutacji β liczb 1, 2, ..., n, mających macierz incydencji B ≤ A. Aby otrzymać informację o liczbie parzystych i nieparzystych permutacji z warunkiem B ≤ A, należy obliczyć dwuskładowy wektor (ɑ1, ɑ2), gdzie ɑ1 + ɑ2 = per A. Ogólniej wprowadzamy pojęcie ω-permanentu, gdzie ω = e2πi/m, który obliczamy jako odpowiedni m-składowy wektor. Dla takich i innych funkcji macierzowych uogólniamy twierdzenie Laplace’a o ich rozwinięciu względem elementów pierwszego wiersza, wykorzystując zdefiniowane w tym celu tak zwane minory kombinatoryczne. W szczególności obliczamy w ten sposób indeks cyklowy permutacji spełniających warunek B ≤ A.

Słowa kluczowe

EN

square matrices; permanent; cycle index of permutations

PL

macierz kwadratowa; permanent; indeks cyklowy permutacji

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Zeszyty Naukowe. Matematyka Stosowana / Politechnika Śląska
• Rocznik: 2014
• Tom: z. 4
• Strony: 5--16
• Opis fizyczny: Bibliogr. 10 poz.

Twórcy

autor

Shevelev V.

• Department of Mathematics. Ben-Gurion University of the Negev

Bibliografia

• 1. Abramowitz M., Stegun I.A.: Handbook on Special Functions. Dover Publ., New York 1972.
• 2. Heinz A., Seqfan Discussion Lists. Aug 3 and 7, 2010.
• 3. Kostrikin A.I.: Introduction to Algebra. Springer, New York 1982.
• 4. Minc H.: Permanents. Addison-Wesley, Reading 1978.
• 5. Riordan J.: An Introduction to Combinatorial Analysis, fourth printing. Wiley, New York 1967.
• 6. Shevelev V.S.: On a method of constructing rook polynomials and some of its applications. Combinatorial Analysis (MSU) 8 (1989), 124–138 (in Russian).
• 7. Shevelev V.S.: Enumerating the permutations with restricted positions and a fixed number of cycles. Diskr. Mat., 4, no. 2 (1992), 3–22 (in Russian).
• 8. Shevelev V.: Computing cyclic indicators of permutations with confined displacements. Dokl. Akad. Nauk of the Ukraine 7 (1993), 35–39.
• 9. Shevelev V.: Development of the rook technique for calculating the cycle indices of (0,1)-matrices. Izvestia Vuzov of the North-Caucasus region, Nature Sciences (Mathematics) 4 (1996), 21–28 (in Russian).
• 10. Sloane N.J.A.: The On-Line Encyclopedia of Integer Sequences. http://oeis.org (2014).