RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor
Subscription

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Diskr. Mat.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Diskr. Mat., 2008, Volume 20, Issue 4, Pages 42–60 (Mi dm1025)  

This article is cited in 10 scientific papers (total in 10 papers)

On ranks, Green classes, and the theory of determinants of Boolean matrices

V. B. Poplavskii


Abstract: We consider the groupoid of all possible matrices over an arbitrary Boolean algebra with partial operation of matrix product. On this groupoid, we define the equivalence classes analogous to the Green classes $H,C,R,D,J$ for semigroups. We introduce the notion of the minor rank of a Boolean matrix. We show that the column, row, factorisation and minor ranks are invariants for the $J$-class of this groupoid, and the minor ranks do not exceed the column, row, factorisation and permanent ranks.
The key result of this work explains the role of the Boolean determinant. We show that in some $J$-class there exists a square $n\times n$ matrix with nonzero determinant if and only if the column, row, factorisation and minor ranks of any matrix of this class are equal to each other and equal to $n$. All $n\times n$ matrices of this $J$-class have equal determinants, while the determinants of the square matrices of greater size are equal to zero.

DOI: https://doi.org/10.4213/dm1025

Full text: PDF file (198 kB)
References: PDF file   HTML file

English version:
Discrete Mathematics and Applications, 2008, 18:6, 641–658

Bibliographic databases:

UDC: 512.643
Received: 10.01.2007

Citation: V. B. Poplavskii, “On ranks, Green classes, and the theory of determinants of Boolean matrices”, Diskr. Mat., 20:4 (2008), 42–60; Discrete Math. Appl., 18:6 (2008), 641–658

Citation in format AMSBIB
\Bibitem{Pop08}
\by V.~B.~Poplavskii
\paper On ranks, Green classes, and the theory of determinants of Boolean matrices
\jour Diskr. Mat.
\yr 2008
\vol 20
\issue 4
\pages 42--60
\mathnet{http://mi.mathnet.ru/dm1025}
\crossref{https://doi.org/10.4213/dm1025}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2500603}
\zmath{https://zbmath.org/?q=an:1184.15020}
\elib{http://elibrary.ru/item.asp?id=20730265}
\transl
\jour Discrete Math. Appl.
\yr 2008
\vol 18
\issue 6
\pages 641--658
\crossref{https://doi.org/10.1515/DMA.2008.049}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-57349141967}


Linking options:
  • http://mi.mathnet.ru/eng/dm1025
  • https://doi.org/10.4213/dm1025
  • http://mi.mathnet.ru/eng/dm/v20/i4/p42

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. V. B. Poplavskii, “O nulyakh opredelitelya bulevykh matrits”, Izv. Sarat. un-ta. Nov. ser. Ser. Matematika. Mekhanika. Informatika, 9:3 (2009), 56–61  mathnet  crossref
    2. I. B. Kozhukhov, V. A. Yaroshevich, “On the potential divisibility of matrices over distributive lattices”, Discrete Math. Appl., 20:3 (2010), 291–305  mathnet  crossref  crossref  mathscinet  zmath  elib
    3. V. B. Poplavskii, “Minor rank, zeros of the determinant of a Boolean matrix, and their applications”, Discrete Math. Appl., 21:5-6 (2011), 613–644  mathnet  crossref  crossref  mathscinet  elib
    4. V. B. Poplavskii, “Formuly Kramera dlya sistem lineinykh uravnenii i neravenstv nad bulevoi algebroi”, Izv. Sarat. un-ta. Nov. ser. Ser. Matematika. Mekhanika. Informatika, 11:3(2) (2011), 43–46  mathnet  crossref
    5. Poplavskii V.B., “Ob opredelitelyakh matrits nad polyami, koltsami i polukoltsami”, Vestn. Mosk. gos. akademii delovogo administrirovaniya. Ser. Filosofskie, sotsialnye i estestvennye nauki, 2011, no. 5, 158–165  elib
    6. V. B. Poplavski, “On applications of associativity of dual compositions in the algebra of Boolean matrices”, J. Math. Sci., 191:5 (2013), 718–725  mathnet  crossref
    7. E. E. Marenich, “Determinant theory for lattice matrices”, J. Math. Sci., 193:4 (2013), 537–547  mathnet  crossref
    8. V. B. Poplavskii, “Ob idempotentakh algebry bulevykh matrits”, Izv. Sarat. un-ta. Nov. ser. Ser. Matematika. Mekhanika. Informatika, 12:2 (2012), 26–33  mathnet  crossref  elib
    9. Ya. N. Shitov, “On Boolean matrices with full factor rank”, Sb. Math., 204:11 (2013), 1691–1699  mathnet  crossref  crossref  mathscinet  zmath  adsnasa  isi  elib  elib
    10. He Q.-B., Li H.-G., Jin M.-M., Duan H.-M., Zhang Q.-H., “New Necessary and Sufficient Condition and Algorithm For Directed Hamiltonian Graph Based on Boolean Determinant Theory”, J. Discret. Math. Sci. Cryptogr., 20:3 (2017), 725–745  crossref  isi  scopus
  • Дискретная математика
    Number of views:
    This page:635
    Full text:149
    References:56
    First page:24

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020