The structure of irreducible matrices †

Let A be an irreducible matrix with index of imprimitivity h is shown that there exists a permutation matrix P such that PAP^t is in a superdiagonal block form with k nonzero blocks if and only if k divides h It is also shown that a matrix in a superdiagonal block form without zero rows or columns is irreducible if and only if the product of the superdiagonal nonzero blocks is irreducible.     

Classification of (v, 3)-configurations

A (v, 3)-configuration is a nondegenerate matrix of dimension v over the field GF(2) considered up to permutation of rows and columns and containing exactly three 1’s in the rows and columns, while the inverse matrix has also exactly three 1’s in the rows and columns. It is proved that, for each even v ≥ 4, there is only one indecomposable (v, 3)-configuration, while, for odd v, there are no such configurations, the only exception being the unique (5, 3)-configuration.     

Linear relations of refined enumerations of alternating sign matrices

In recent papers we have studied refined enumerations of alternating sign matrices with respect to a fixed set of top and bottom rows. The present paper is a first step towards extending these considerations to alternating sign matrices where in addition some left and right columns are fixed. The main result is a simple linear relation between the number of n×n alternating sign matrices where the top row as well as the left and the right column is fixed and the number of n×n alternating sign matrices where the two top rows and the bottom row are fixed. This may be seen as a first indication for the fact that the refined enumerations of alternating sign matrices with respect to a fixed set of top and bottom rows as well as left and right columns can possibly be reduced to the refined enumerations where only some top and bottom rows are fixed. For the latter numbers we provide a system of linear equations that conjecturally determines them uniquely.     

There is no (46, 6, 1) block design*

Abstact: In this paper we show that a (46, 6, 1) design does not exist. This result was obtained by a computer search. In the incidence matrix of such a design, there must exist a “c4” configuration—6 rows and 4 columns, in which each pair of columns intersect exactly once, in distinct rows. There can also exist a “c5” configuration with 10 rows and 5 columns, in which each pair of columns intersect exactly once, in distinct rows. Thus the search for (46, 6, 1) designs can be subdivided into two cases, the first of which assumes there is no “c5”, and the second of which assumes there is a “c5”. After completing the searches for both cases, we found no (46, 6, 1) design. © 2000 John Wiley & Sons, Inc. J Combin Designs 9: 60–71, 2001     

Linear Codes with Non-Uniform Error Correction Capability

This paper introduces a class of linear codes which are non-uniform error correcting, i.e. they have the capability of correcting different errors in different code words. A technique for specifying error characteristics in terms of algebraic inequalities, rather than the traditional spheres of radius e, is used. A construction is given for deriving these codes from known linear block codes. This is accomplished by a new method called parity sectioned reduction. In this method, the parity check matrix of a uniform error correcting linear code is reduced by dropping some rows and columns and the error range inequalities are modified.     

Clustering Methods in Microarrays

Summary DCT Given a finite set of points in an Euclidean space the \emph{spanning tree} is a tree of minimal length having the given points as vertices. The length of the tree is the sum of the distances of all connected point pairs of the tree. The clustering tree with a given length of a given finite set of points is the spanning tree of an appropriately chosen other set of points approximating the given set of points with minimal sum of square distances among all spanning trees with the given length. DCM A matrix of real numbers is said to be column monotone orderable if there exists an ordering of columns of the matrix such that all rows of the matrix become monotone after ordering. The {\emph{monotone sum of squares of a matrix}} is the minimum of sum of squares of differences of the elements of the matrix and a column monotone orderable matrix where the minimum is taken on the set of all column monotone orderable matrices. Decomposition clusters of monotone orderings of a matrix is a clustering ofthe rows of the matrix into given number of clusters such that thesum of monotone sum of squares of the matrices formed by the rowsof the same cluster is minimal.DCP A matrix of real numbers is said to be column partitionable if there exists a partition of the columns such that the elements belonging to the same subset of the partition are equal in each row. Given a partition of the columns of a matrix the partition sum of squares of the matrix is the minimum of the sum of square of differences of the elements of the matrix and a column partitionable matrix where the minimum is taken on the set of all column partitionable matrices. Decomposition of the rows of a matrix into clusters of partitions is the minimization of the corresponding partition sum of squares given the number of clusters and the sizes of the subsets of the partitions.     

An approach to defining the pattern of interaction effects in a two-way layout

Summary A method is given to classify rows and columns into subgroups so that additivity holds within each of the subtables made of the grouped rows or the grouped columns. The least squares estimators of the cell means are easily obtained for the resulting linear model together with their variances. An estimator of the error varianceσ ₂ is given when there is only one observation per cell. A treatment of an ordered table is also given.     

A central limit theorem for extremal characters of the infinite symmetric group

The asymptotic behavior of the lengths of the first rows and columns in the random Young diagrams corresponding to extremal characters of the infinite symmetric group is studied. We consider rows and columns with linear growth in n and prove a central limit theorem for their lengths in the case of distinct Thoma parameters. We also prove a more precise statement relating the growth of rows and columns of Young diagrams to a simple independent random sampling model.     

Optimal simplex tableau characterization of unique and bounded solutions of linear programs

Uniqueness and boundedness of solutions of linear programs are characterized in terms of an optimal simplex tableau. LetM denote the submatrix in an optimal simplex tableau with columns corresponding to degenerate optimal dual basic variables. A primal optimal solution is unique iff there exists a nonvacuous nonnegative linear combination of the rows ofM, corresponding to degenerate optimal primal basic variables, which is positive. The set of primal optimal solutions is bounded iff there exists a nonnegative linear combination of the rows ofM which is positive. WhenM is empty, the primal optimal solution is unique.This research was sponsored by the United States Army under Contract No. DAAG29-75-C-0024. This material is based upon work supported by the National Science Foundation under Grant No. MCS-79-01066.     

On completely irreducible operators

Let T be a bounded linear operator on Hilbert space H, M an invariant subspace of T. If there exists another invariant subspace N of T such that H = M + N and M ∩ N = 0, then M is said to be a completely reduced subspace of T. If T has a nontrivial completely reduced subspace, then T is said to be completely reducible; otherwise T is said to be completely irreducible. In the present paper we briefly sum up works on completely irreducible operators that have been done by the Functional Analysis Seminar of Jilin University in the past ten years and more. The paper contains four sections. In section 1 the background of completely irreducible operators is given in detail. Section 2 shows which operator in some well-known classes of operators, for example, weighted shifts, Toeplitz operators, etc., is completely irreducible. In section 3 it is proved that every bounded linear operator on the Hilbert space can be approximated by the finite direct sum of completely irreducible operators. It is clear that a completely irreducible operator is a rather suitable analogue of Jordan blocks in L(H), the set of all bounded linear operators on Hilbert space H. In section 4 several questions concerning completely irreducible operators are discussed and it is shown that some properties of completely irreducible operators are different from properties of unicellular operators. __________ Translated from Acta Sci. Nat. Univ. Jilin, 1992, (4): 20–29     

On the upper bounds of the minimum number of rows of disjunct matrices

A 0-1 matrix is d-disjunct if no column is covered by the union of any d other columns. A 0-1 matrix is (d; z)-disjunct if for any column C and any d other columns, there exist at least z rows such that each of them has value 1 at column C and value 0 at all the other d columns. Let t(d, n) and t(d, n; z) denote the minimum number of rows required by a d-disjunct matrix and a (d; z)-disjunct matrix with n columns, respectively. We give a very short proof for the currently best upper bound on t(d, n). We also generalize our method to obtain a new upper bound on t(d, n; z). The work of Y. Cheng and G. Lin is supported by Natural Science and Engineering Research Council (NSERC) of Canada, and the Alberta Ingenuity Center for Machine Learning (AICML) at the University of Alberta. The work of D.-Z. Du is partially supported by National Science Foundation under grant No.CCF0621829.     

Defining the Determinant-like Function for m by n Matrices Using the Exterior Algebra

In this paper, we present a function called the Determinant-Like Function that generalises the determinant function to m by n matrices using the Clifford algebra C?(V, 0). By definition, this generalisation satisfies the property that the exterior product of its column vectors has a magnitude that equals its determinant-like function if it has more rows than columns. For matrices which have more columns than rows, we make use of another property that the exterior product of its rows has a magnitude that equals the absolute value of its determinant-like function if it has more columns than rows. Defining the sign of this determinant-like function remains an open question.     

Line Insertions in Totally Positive Matrices

It is obvious that between any two rows (columns) of an m-by-n totally nonnegative matrix a new row (column) may be inserted to form an (m+1)-by-n (m-by-(n+1)) totally nonnegative matrix. The analogous question, in which “totally nonnegative” is replaced by “totally positive” arises, for example, in completion problems and in extension of collocation matrices, and its answer is not obvious. Here, the totally positive case is answered affirmatively, and in the process an analysis of totally positive linear systems, that may be of independent interest, is used.     

Pooling, lattice square, and union jack designs

Simplified pooling designs employ rows, columns, and principal diagonals from square and rectangular plates. The requirement that every two samples be tested together in exactly one pool leads to a novel combinatorial configuration: The union jack design. Existence of union jack designs is settled affirmatively whenever the ordern is a prime andn3 (mod 4).     

Deriving compact extended formulations via LP-based separation techniques

The best formulations for some combinatorial optimization problems are integer linear programming models with an exponential number of rows and/or columns, which are solved incrementally by generating missing rows and columns only when needed. As an alternative to row generation, some exponential formulations can be rewritten in a compact extended form, which have only a polynomial number of constraints and a polynomial, although larger, number of variables. As an alternative to column generation, there are compact extended formulations for the dual problems, which lead to compact equivalent primal formulations, again with only a polynomial number of constraints and variables. In this this paper we introduce a tool to derive compact extended formulations and survey many combinatorial optimization problems for which it can be applied. The tool is based on the possibility of formulating the separation procedure by an LP model. It can be seen as one further method to generate compact extended formulations besides other tools of geometric and combinatorial nature present in the literature.     

A classification of upper equivalent matrices the generic case

Two square matricesA andB are called upper equivalent iff there exists an invertible lower triangular matrixL such thatL ^–1 AL andB have the same upper triangular parts. In this paper we obtain a set of invariants for this equivalence relation. In the case when any minor of a matrixA, in the intersection of its last columns and first rows and contained in its upper triangular part is different from zero, it is shown that the above mentioned set of invariants completely determines the upper triangular parts of the matrices from the equivalence class ofA. Simple representatives for this class are also given.     

On the complement of the Richardson orbit

We consider parabolic subgroups of a general linear group over an algebraically closed field k whose Levi part has exactly t factors. By a classical theorem of Richardson, the nilradical of a parabolic subgroup P has an open dense P-orbit. In the complement to this dense orbit, there are infinitely many orbits as soon as the number t of factors in the Levi part is ≥6. In this paper, we describe the irreducible components of the complement. In particular, we show that there are at most t ? 1 irreducible components. We are also able to determine their codimensions.     

Characterization and linear-time detection of minimal obstructions to concave-round graphs and the circular-ones property

A graph is concave-round if its vertices can be circularly enumerated so that the closed neighborhood of each vertex is an interval in the enumeration. In this study, we give a minimal forbidden induced subgraph characterization for the class of concave-round graphs, solving a problem posed by Bang-Jensen, Huang, and Yeo [SIAM J. Discrete Math., 13 (2000), pp. 179–193]. In addition, we show that it is possible to find one such forbidden induced subgraph in linear time in any given graph that is not concave-round. As part of the analysis, we obtain characterizations by minimal forbidden submatrices for the circular-ones property for rows and for the circular-ones property for rows and columns and show that, also for both variants of the property, one of the corresponding forbidden submatrices can be found (if present) in any given matrix in linear time. We make some final remarks regarding connections to some classes of circular-arc graphs.     

Block-iterative methods for consistent and inconsistent linear equations

Summary We shall in this paper consider the problem of computing a generalized solution of a given linear system of equations. The matrix will be partitioned by blocks of rows or blocks of columns. The generalized inverses of the blocks are then used as data to Jacobi- and SOR-types of iterative schemes. It is shown that the methods based on partitioning by rows converge towards the minimum norm solution of a consistent linear system. The column methods converge towards a least squares solution of a given system. For the case with two blocks explicit expressions for the optimal values of the iteration parameters are obtained. Finally an application is given to the linear system that arises from reconstruction of a two-dimensional object by its one-dimensional projections.