A factorization theorem for a certain class of graphs

In this note we give a necessary and sufficient condition for factorization of graphs satisfying the “odd cycle property”. We show that a graph G with the odd cycle property contains a [k_i] factor if and only if the sequence [H]+[k_i] is graphical for all subgraphs H of the complement of G.A similar theorem is shown to be true for all digraphs.     

The proof of Ushio''''s conjecture concerning path factorization of complete bipartite graphs

Let Km,n be a complete bipartite graph with two partite sets having m and n vertices, respectively. A Pv-factorization of Km,n is a set of edge-disjoint Pv-factors of Km,n which partition the set of edges of Km,n. When v is an even number, Wang and Ushio gave a necessary and sufficient condition for existence of Pv-factorization of Km,n. When k is an odd number, Ushio in 1993 proposed a conjecture. Very recently, we have proved that Ushio's conjecture is true when v = 4k-1. In this paper we shall show that Ushio Conjecture is true when v = 4k 1, and then Ushio's conjecture is true. That is, we will prove that a necessary and sufficient condition for the existence of a P4k 1-factorization of Km,n is (i) 2km≤ (2k 1)n, (ii) 2kn≤ (2k 1)m, (iii) m n = 0 (mod 4k 1), (iv) (4k 1)mn/[4k(m n)] is an integer.     

The proof of Ushio’s conjecture concerning path factorization of complete bipartite graphs

Let K _m,n be a complete bipartite graph with two partite sets having m and n vertices, respectively. A P _v -factorization of K _m,n is a set of edge-disjoint P _v -factors of K _m,n which partition the set of edges of K _m,n . When v is an even number, Wang and Ushio gave a necessary and sufficient condition for existence of P _v -factorization of K _m,n . When k is an odd number, Ushio in 1993 proposed a conjecture. Very recently, we have proved that Ushio’s conjecture is true when v = 4k − 1. In this paper we shall show that Ushio Conjecture is true when v = 4k − 1, and then Ushio’s conjecture is true. That is, we will prove that a necessary and sufficient condition for the existence of a P _4k+1-factorization of K _m,n is (i) 2km≤(2k+1)n, (ii) 2kn≤(2k+1)m, (iii) m+n≡0 (mod 4k+1), (iv) (4k+1)mn/[4k(m+n)] is an integer.     

Set-functions and factorization

Both authors were supported by grants from the National Science Foundation     

Holomorphic factorization of polynomials

We give necessary and sufficient conditions for a holomorphic factorization of an irreducible polynomial P(s, λ), s ∈ Cⁿ, λ ∈ C, in a domain Ω ? Cⁿ which is connected with the ordering of the real part of the roots of the equation P(s, λ) = 0, s ∈ Ω.     

Idempotent factorization of matrices

Necessary and sufficient conditions are presented for a square matrix over an arbitrary field to be a product of k ≥ 1 idempotent matrices of prescribed nullities.     

Modern factorization methods

In this expository paper the progress in factorization of large integers since the introduction of computers is reported. Thanks to theoretical advances and refinements, as well as to more powerful computers, the practical limit of integers possible to factor has been raised considerably during the past 20 years. The present practical limit is around 10⁷⁵ if supercomputers are used and if much computer time is available.     

Angular factorization of matrices

Let Q denote a selfadjoint matrix (or operator of finite rank). The factorization of I + Q into the form $\text{I + Q = (I ? W) D(I ? W}{}^1\text{)}$ is considered. The well-known case where W is constrained to be lower triangular while D is diagonal is extended to quadrangular and other generalized-canonical forms. The case where Q is not selfadjoint is also developed. Applications for these results may be found in the realm of multivariate-stochastic approximation, and signal extraction.     

Multidimensional butterfly factorization

This paper introduces the multidimensional butterfly factorization as a data-sparse representation of multidimensional kernel matrices that satisfy the complementary low-rank property. This factorization approximates such a kernel matrix of size $N\times N$ with a product of $O(\log ?N)$ sparse matrices, each of which contains $O(N)$ nonzero entries. We also propose efficient algorithms for constructing this factorization when either (i) a fast algorithm for applying the kernel matrix and its adjoint is available or (ii) every entry of the kernel matrix can be evaluated in $O(1)$ operations. For the kernel matrices of multidimensional Fourier integral operators, for which the complementary low-rank property is not satisfied due to a singularity at the origin, we extend this factorization by combining it with either a polar coordinate transformation or a multiscale decomposition of the integration domain to overcome the singularity. Numerical results are provided to demonstrate the efficiency of the proposed algorithms.     

Nilpotent factorization of matrices

We show that, with the exception of 2 × 2 nonzero nilpotent matrices, every singular square matrix over an arbitrary field is a product of two nilpotent matrices.     

Clique graphs of time graphs

A simple, finite graph G is called a time graph (equivalently, an indifference graph) if there is an injective real function f on the vertices v(G) such that v_iv_j ∈ e(G) for v_i ≠ v_j if and only if |f(v_i) ? f(v_j)| ≤ 1. A clique of a graph G is a maximal complete subgraph of G. The clique graph K(G) of a graph G is the intersection graph of the cliques of G. It will be shown that the clique graph of a time graph is a time graph, and that every time graph is the clique graph of some time graph. Denote the clique graph of a clique graph of G by K²(G), and inductively, denote K(K^m?1(G)) by K^m(G). Define the index indx(G) of a connected time graph G as the smallest integer n such that Kⁿ(G) is the trivial graph. It will be shown that the index of a time graph is equal to its diameter. Finally, bounds on the diameter of a time graph will be derived.     

Lyndon factorization of sturmian words

We express any general characteristic sturmian word as a unique infinite non-increasing product of Lyndon words. Using this identity, we give a new ω-division for characteristic sturmian words. We also give a short proof of a result by Berstel and de Luca (Sturmian words, Lyndon words and trees, Theoret. Comput. Sci., 178 (1997) 171–203.); more precisely, we show that the set of factors of sturmian words that qualify as Lyndon words is the set of primitive Christoffel words.     

On palindromic factorization of words

Given a finite word u, we define its palindromic length  _|u|pal${|u|}_{\mathrm{pal}}$ to be the least number n   such that u=_v1v2…_vn$u=v_1{v}_2\dots v_n$ with each _vi$v_i$ a palindrome. We address the following open question: let P be a positive integer and w   an infinite word such that _|u|pal?P${|u|}_{\mathrm{pal}}?P$ for every factor u of w. Must w be ultimately periodic? We give a partial answer to this question by proving that for each positive integer k, the word w must contain a k  -power, i.e., a factor of the form u^k$u^k$. In particular, w cannot be a fixed point of a primitive morphism. We also prove more: for each pair of positive integers k and l, the word w must contain a position covered by at least l distinct k-powers. In particular, w cannot be a Sierpinski-like word.     

Crossing graphs of fiber-complemented graphs

Fiber-complemented graphs form a vast non-bipartite generalization of median graphs. Using a certain natural coloring of edges, induced by parallelism relation between prefibers of a fiber-complemented graph, we introduce the crossing graph of a fiber-complemented graph G as the graph whose vertices are colors, and two colors are adjacent if they cross on some induced 4-cycle in G. We show that a fiber-complemented graph is 2-connected if and only if its crossing graph is connected. We characterize those fiber-complemented graphs whose crossing graph is complete, and also those whose crossing graph is chordal.     

Unique tensor factorization of algebras

Tensor product decomposition of algebras is known to be non-unique in many cases. But, as will be shown here, a -indecomposable, finite-dimensional -algebra A has an essentially unique tensor factorization into non-trivial, -indecomposable factors . Thus the semiring of isomorphism classes of finite-dimensional -algebras is a polynomial semiring . Moreover, the field of complex numbers can be replaced by an arbitrary field of characteristic zero if one restricts oneself to schurian algebras. Received: 5 October 1998     

QR factorization of Toeplitz matrices

Summary This paper presents a new algorithm for computing theQR factorization of anm×n Toeplitz matrix inO(mn) operations. The algorithm exploits the procedure for the rank-1 modification and the fact that both principal (m–1)×(n–1) submatrices of the Toeplitz matrix are identical. An efficient parallel implementation of the algorithm is possible.