The Redheffer matrix of a partially ordered set (Q1773154)

From MaRDI portal
scientific article
Language Label Description Also known as
English
The Redheffer matrix of a partially ordered set
scientific article

    Statements

    The Redheffer matrix of a partially ordered set (English)
    0 references
    0 references
    25 April 2005
    0 references
    Let \(R_n\) be \textit{R. Redheffer}'s matrix \((a_{ij})_{1\leq i,j\leq n}\) with \(a_{ij}=1\) if and only if \(i| j\) or if \(j=1\), and \(a_{ij} =0\) otherwise [Int. Ser. Numer. Math. 36, 213--216 (1977; Zbl 0363.65062)]. The author gives a short simultaneous proof of the identities \[ \det R_n =\sum_{j=1}^{n} f_{-}(j)=\sum_{j=1}^{n} \mu (j), \tag{1} \] \[ \text{perm} \,R_n =\sum_{j=1}^{n} f_{1}(j) \tag{2} \] with \[ f_{r}(1)=1,\quad f_{r}(k)=\sum_{\substack{ l>1\\ k=d_1> \cdots >d_l =1\\ 1< i< l \Rightarrow d_i | d_{i-1}}} r^{l-1} \quad (k>1,\;r = 1,-1) \] and generalizes (1) to finite partially ordered sets that have a 0 element. He remarks that \textit{Vladeta Jovovic} has found (2) in 2003 [Sequence A025523, \textit{N. J. A. Sloane}'s On-Line Encyclopedia of Integer Sequences, Notices Am. Math. Soc. 50, 912--915 (2003; Zbl 1044.11108)].
    0 references
    exact enumeration problems
    0 references
    algebraic
    0 references
    combinatorics
    0 references
    determinant
    0 references
    permanent
    0 references
    identities
    0 references
    Redneffer matrix
    0 references
    partially ordered set
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references