Solving capacitated clustering problems

This paper presents two effective algorithms for clustering n entities into p mutually exclusive and exhaustive groups where the ‘size’ of each group is restricted. As its objective, the clustering model minimizes the sum of distance between each entity and a designated group median. Empirical results using both a primal heuristic and a hybrid heuristic-subgradient method for problems having n ? 100 (i.e. 10 100 binary variables) show that the algorithms locate close to optimal solutions without resorting to tree enumeration. The capacitated clustering model is applied to the problem of sales force territorial design.     

Subspaces of matrices with special rank properties

Let K be a field and let M_m×n(K) denote the space of m×n matrices over K. We investigate properties of a subspace M of M_m×n(K) of dimension n(m-r+1) in which each non-zero element of M has rank at least r and enumerate the number of elements of a given rank in M when K is finite. We also provide an upper bound for the dimension of a constant rank r subspace of M_m×n(K) when K is finite and give non-trivial examples to show that our bound is optimal in some cases. We include a similar a bound for the maximum dimension of a constant rank subspace of skew-symmetric matrices over a finite field.     

Rank-based selection strategies for the random walk process

In many decision situations such as hiring a secretary, selling an asset, or seeking a job, the value of each offer, applicant, or choice is assumed to be an independent, identically distributed random variable. In this paper, we consider a special case where the observations are auto-correlated as in the random walk model for stock prices. For a given random walk process of n observations, we explicitly compute the probability that the j-th observation in the sequence is the maximum or minimum among all n observations. Based on the probability distribution of the rank, we derive several distribution-free selection strategies under which the decision maker's expected utility of selecting the best choice is maximized. We show that, unlike in the classical secretary problem, evaluating more choices in the random walk process does not increase the likelihood of successfully selecting the best.     

Graphs in which each m-tuple of vertices is adjacent to the same number n of other vertices

Let G be a finite graph in which each m-tuple of mutually distinct vertices is adjacent to exactly n other vertices. If m ≥3 then G is isomorphic to the complete m+n graph. For completeness we state the friendship theorem of Erdös, Rényi, and Sós and a theorem of Bose and Shrikhande, both of which deal with the case m=2.     

Eigenvalues and invariants of tensors

A tensor is represented by a supermatrix under a co-ordinate system. In this paper, we define E-eigenvalues and E-eigenvectors for tensors and supermatrices. By the resultant theory, we define the E-characteristic polynomial of a tensor. An E-eigenvalue of a tensor is a root of the E-characteristic polynomial. In the regular case, a complex number is an E-eigenvalue if and only if it is a root of the E-characteristic polynomial. We convert the E-characteristic polynomial of a tensor to a monic polynomial and show that the coefficients of that monic polynomial are invariants of that tensor, i.e., they are invariant under co-ordinate system changes. We call them principal invariants of that tensor. The maximum number of principal invariants of mth order n-dimensional tensors is a function of m and n. We denote it by d(m,n) and show that d(1,n)=1, d(2,n)=n, d(m,2)=m for m?3 and d(m,n)?mn−1+?+m for m,n?3. We also define the rank of a tensor. All real eigenvectors associated with nonzero E-eigenvalues are in a subspace with dimension equal to its rank.     

Binary tree algebraic computation and parallel algorithms for simple graphs

In this paper we define the binary tree algebraic computation (BTAC) problem and develop an efficient parallel algorithm for solving this problem. A variety of graph problems (minimum covering set, minimum r-dominating set, maximum matching set, etc.) for trees and two terminal series parallel (TTSP) graphs can be converted to instances of the BTAC problem. Thus efficient parallel algorithms for these problems are obtained systematically by using the BTAC algorithm. The parallel computation model is an exclusive read exclusive write PRAM. The algorithms for tree problems run in O(log n) time with O(n) processors. The algorithms for TTSP graph problems run in O(log m) time with O(m) processors where n (m) is the number of vertices (edges) in the input graph. These algorithms are within an O(log n) factor of optimal.     

A remark on full rank perfect codes

Any full rank perfect 1-error correcting binary code of length n=2^k-1 and with a kernel of dimension n-log(n+1)-m, where m is sufficiently large, may be used to construct a full rank perfect 1-error correcting binary code of length 2^m-1 and with a kernel of dimension n-log(n+1)-k. Especially we may construct full rank perfect 1-error correcting binary codes of length n=2^m-1 and with a kernel of dimension n-log(n+1)-4 for m=6,7,…,10.This result extends known results on the possibilities for the size of a kernel of a full rank perfect code.     

Exact Matrix Completion via Convex Optimization

We consider a problem of considerable practical interest: the recovery of a data matrix from a sampling of its entries. Suppose that we observe m entries selected uniformly at random from a matrix M. Can we complete the matrix and recover the entries that we have not seen? We show that one can perfectly recover most low-rank matrices from what appears to be an incomplete set of entries. We prove that if the number m of sampled entries obeys $m\ge C\,n^{1.2}r\log n$ for some positive numerical constant C, then with very high probability, most n×n matrices of rank r can be perfectly recovered by solving a simple convex optimization program. This program finds the matrix with minimum nuclear norm that fits the data. The condition above assumes that the rank is not too large. However, if one replaces the 1.2 exponent with 1.25, then the result holds for all values of the rank. Similar results hold for arbitrary rectangular matrices as well. Our results are connected with the recent literature on compressed sensing, and show that objects other than signals and images can be perfectly reconstructed from very limited information.     

On the plane term rank of three dimensional matrices

It is shown that if A is a p>×q×r matrix such that each of the horizontal plane sections of A has full term rank, then the plane term rank of A is greater than m?√m where m= min {p,q,r}. In particular, if A is a three dimensional line stochastic matrix of order n, then the plane term rank of A is greater than n?√n.     

Linear operators that preserve Boolean rank of Boolean matrices

The Boolean rank of a nonzero m × n Boolean matrix A is the minimum number k such that there exist an m× k Boolean matrix B and a k × n Boolean matrix C such that A = BC. In the previous research L. B. Beasley and N. J. Pullman obtained that a linear operator preserves Boolean rank if and only if it preserves Boolean ranks 1 and 2. In this paper we extend this characterizations of linear operators that preserve the Boolean ranks of Boolean matrices. That is, we obtain that a linear operator preserves Boolean rank if and only if it preserves Boolean ranks 1 and k for some 1 < k ? m.     

Interaction information and Markov chain

The problem of multivariate information analysis is considered. First, the interaction information in each dimension is defined analogously according to McGill [4] and then applied to Markov chains. The property of interaction information zero deeply relates to a certain class of weakly dependent random variables. For homogeneous, recurrent Markov chains with m states, m ≥ n ≥3, the zero criterion of n-dimensional interaction information is achieved only by (n ? 2)-dependent Markov chains, which are generated by some nilpotent matrices. Further for Gaussian Markov chains, it gives the decomposition rule of the variables into mutually correlated subchains.     

A characterization of the one parameter exponential family of distributions by monotonicity of likelihood ratios

Summary Any one parameter exponential family of distributions has monotone likelihood ratios. As the product probabilities of n identical distributions of an exponential family form again an exponential family, it has monotone likelihood ratios for arbitrary n. Furthermore, the members of an exponential family are mutually absolutely continuous. In Part 1, we show that these properties uniquely characterize the exponential family. The application of this result to the theory of testing hypotheses (Part 2) shows that if a family of mutually absolutely continuous distributions has uniformly most powerful tests for arbitrary levels of significance, and arbitrary sample sizes, then it is necessarily an exponential family.The research was done while this author was a Visiting Professor in the Department of Statistics at the University of Chicago. It was supported by Research Grants Nos. NSF-G10368 and NSF-G21058 from the Division of Mathematical, Physical and Engineering Sciences of the National Science Foundation.     

A new technique for linear static state estimation based on weighted least absolute value approximations

This paper presents a new technique for solving the problem of linear static state estimation, based on weighted least absolute value (WLAV). A set ofm optimality equations is obtained, wherem=number of measurements, based on minimizing a WLAV performance index involvingn unknown state variables,m>n. These equations are solved using the left pseudo-inverse transformation, least-square sense, to obtain approximately the residual of each measurement.Ifk is the rank of the matrixH,k=n, we choose among the optimality equations a number of equations equal to the rankk and having the smallest residuals. The solution of thesen equations inn unknowns yields the best WLAV estimation. A numerical example is reported; the results for this example are obtained by using both WLS and WLAV techniques. It is shown that the best WLAV approximation is superior to the best WLS approximation when estimating the true form of data containing some inaccurate observations.This work was supported by the Natural Science and Engineering Research Council of Canada, Grant No. A4146.     

The extent to which triangular sub-patterns explain minimum rank

For any zero-nonzero pattern of a matrix, the minimum possible rank is at least the size of a sub-pattern that is permutation equivalent to a triangular pattern with nonzero diagonal. For certain numbers of rows and columns, the minimum rank of a pattern is k only when there is a k-by-k such triangle. Here, we complete the determination of such sizes by showing that an m-by-n pattern of minimum rank k must contain a k-triangle for m=5, k=4; m=6, k=5; and m=6, k=4. A table is given showing whether or not this happens for all m, n, k. In the process, a Schur complement approach to minimum rank is described and used, and simple ways to recognize the presence of triangles of sizes less than 7 are given.     

On the measurable chromatic number of a space of dimension n ≤ 24

This paper is devoted to the classical problem of finding the measurable chromatic number of n-dimensional Euclidean space, i.e., the value χ _m (? ⁿ ) equal to the least possible number of Lebesgue measurable sets that do not contain pairs of points at a distance of 1 and cover the whole space. Assuming that a certain hypothesis is true, we significantly improve the lower bounds for χ _m (? ⁿ ).     

2-Adic valuations of certain ratios of products of factorials and applications

We prove the conjecture of Falikman-Friedland-Loewy on the parity of the degrees of projective varieties of n×n complex symmetric matrices of rank at most k. We also characterize the parity of the degrees of projective varieties of n×n complex skew symmetric matrices of rank at most 2p. We give recursive relations which determine the parity of the degrees of projective varieties of m×n complex matrices of rank at most k. In the case the degrees of these varieties are odd, we characterize the minimal dimensions of subspaces of n×n skew symmetric real matrices and of m×n real matrices containing a nonzero matrix of rank at most k. The parity questions studied here are also of combinatorial interest since they concern the parity of the number of plane partitions contained in a given box, on the one hand, and the parity of the number of symplectic tableaux of rectangular shape, on the other hand.     

On Subsets with Cardinalities of Intersections Divisible by a Fixed Integer

If m(n, l) denotes the maximum number of subsets of an n-element set such that the intersection of any two of them has cardinality divisible by l, then a trivial construction shows that

$m(n,l)\ge 2^{[n/l]}$

For l= 2, this was known to be essentially best possible. For l ? 3, we show by construction that m(n, l)2^?[n/l] grows exponentially in n, and we provide upper bounds.     

Some mutually disjoint steiner systems

A t-design λ; t-d-n is a system of subsets of size d (called blocks) from an n-set S, such that each t-subset from S is contained in precisely λ blocks. A Steiner system S(l, m, n) is a t-design with parameters 1; l-m-n. Two Steiner systems (or t-designs) are disjoint if they share no blocks. A search has been conducted which resulted in discovering 9 mutually disjoint S(5, 8, 24)'s, 24 mutually disjoint S(4, 7, 23)'s, 60 mutually disjoint S(3, 6, 22)'s, and 197 mutually disjoint S(2, 5, 21)'s. Taking unions of several mutually disjoint Steiner systems will then produce t-designs (with varying λ's) on 21, 22, 23, and 24 points.     

Isolation number versus Boolean rank

Let $\mathbb{B}$ be the binary Boolean algebra. The Boolean rank, or factorization rank, of a matrix A in $M_{m\text{,}n}(\mathbb{B})$ is the smallest k such that A can be factored as an $m\times k$ times a $k\times n$ matrix. The isolation number of a matrix, A, is the largest number of entries equal to 1 in the matrix such that no two ones are in the same row, no two ones are in the same column, and no two ones are in a submatrix of A of the form $\left[\begin{array}{cc}\hfill 1\hfill & \hfill 1\hfill \\ \hfill 1\hfill & \hfill 1\hfill \end{array}\right]$. It is known that the isolation number of A is always at most the Boolean rank. This paper investigates for each k, if the isolation number of A is k what are some of the possible values of the Boolean rank of A.     

Bijective linear maps on semimodules spanned by Boolean matrices of fixed rank

Let M_m,n(B) be the semimodule of all m×n Boolean matrices where B is the Boolean algebra with two elements. Let k be a positive integer such that 2?k?min(m,n). Let B(m,n,k) denote the subsemimodule of M_m,n(B) spanned by the set of all rank k matrices. We show that if T is a bijective linear mapping on B(m,n,k), then there exist permutation matrices P and Q such that T(A)=PAQ for all A∈B(m,n,k) or m=n and T(A)=PA^tQ for all A∈B(m,n,k). This result follows from a more general theorem we prove concerning the structure of linear mappings on B(m,n,k) that preserve both the weight of each matrix and rank one matrices of weight k². Here the weight of a Boolean matrix is the number of its nonzero entries.