Linear transformations that preserve the assignment (Q1344072)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Linear transformations that preserve the assignment |
scientific article |
Statements
Linear transformations that preserve the assignment (English)
0 references
5 September 1995
0 references
The structure of linear transformations on the set of real square matrices which preserve the assignment is emphasized. Two vectors of positive integers \(R = (r_ 1, \dots, r_ n)\) and \(S = (s_ 1, \dots, s_ n)\) are considered, where \(\sum^ n_{i=1} r_ i = \sum^ n_{j=1} s_ j = k\) for \(n + 1 \leq k \leq n^ 2\) and \(n \geq 3\); \({\mathcal U} (R,S)\) denotes the set of all \(n \times n\) matrices of 0's and 1's with row sums \(r_ i\) and column sums \(s_ j\), \(i,j = 1, \dots, n\). The vectors \(R\) and \(S\) are said to be compatible if, given any four positive integers \(1 \leq i\), \(j,k\) \(l \geq n\) with \(i \neq k\) and \(j \neq l\), there exists \(A \in {\mathcal U} (R,S)\) such that \(a_{ij} = a_{kl} = 1\) and \(a_{il} = a_{kj} = 0\). The \((R,S)\) assignment function \(P_{R,S} (\cdot)\) is defined by \(P_{R,S} (X) = \sum_{A = {\mathcal U} (R,S)} \prod_{(i,j) \in \text{supp} (A)}x_{ij}\) for any matrix \(X = [x_{ij}] \in M_ n (\mathbb{R})\), where \(\text{supp} (A) = \{(i,j) : a_{ij} \neq 0\}\). If \(k = n\) then \({\mathcal U} (R,S) = S_ n\) and the assignment function is the permanent. The linear transformation \(T : M_ n (\mathbb{R}) \to M_ n (\mathbb{R})\) preserves the assignment if \(P_{R,S} (X) = P_{R,S} (T(X))\) for any \(X \in M_ n (\mathbb{R})\). The main result of the article is obtained for \(R\) and \(S\) compatible and \(2 \leq r_ i\), \(s_ j < n\). It is shown that \(T\) preserves the assignment function \(P_{R,S}\) if and only if \(T(X) = PDXLQ\) for any \(X \in M_ n (\mathbb{R})\) or \(R = S\) and \(T(X) = PDX^ t LQ\) for any \(X \in M_ n (\mathbb{R})\), where \(P\) and \(Q\) are permutation matrices such that \(PR^ t = R^ t\) and \(SQ = S\), \(D = \text{diag} \{d_ 1, \dots, d_ n\}\), \(L = \text{diag} \{l_ l, \dots, l_ n\}\) and \(\prod^ n_{i=1} d_ i^{r_ i} \cdot \prod^ n_{j=1} l_ j^{s_ j} = 1\). It is stated that the result is false if some \(r_ i\) or \(s_ j\) are equal to \(n\) and the problems when some \(r_ i\) or \(s_ j\) are equal to \(1\) or if \(R\) and \(S\) are not compatible remain open.
0 references
assignment preserver
0 references
linear transformations
0 references
assignment function
0 references
permanent
0 references