Tits form numbers

We define the relative Tits form number W(G, V) of a valued bigraph G at a vertex v and derive some basic properties. We give a detailed analysis of the case when W (G,V) ≥½. The properties of these numbers were used without proof in the classification of Auslander algebras of finite representation type [IPTZ]     

研究四色问题的意义及理论构想

四色问题又称四色猜想,是世界近代三大数学难题之一．1976年两位美国数学家Appel与Haken借助计算机给出了一个证明．时至今日,四色问题的正确性早已得到数学界所承认．但是围绕它的非计算机证明,在近几十年来涌现出了各种不同的研究成果．一方面丰富了图论的内容,另一方面又促进了图的染色理论的发展．本文从研究四色问题的意义出发;揭示了四色问题所隐藏的深刻规律,在此基础上提出了一个比四色问题更具有广泛意义的理论构想．主要目地为四色问题的非计算机证明提供一个研究方向．     

The reciprocal of the weighted geometric mean of many positive numbers is a Stieltjes function

In the paper, by the Cauchy integral formula in the theory of complex functions, an integral representation for the reciprocal of the weighted geometric mean of many positive numbers is established. As a result, the reciprocal of the weighted geometric mean of many positive numbers is verified to be a Stieltjes function and, consequently, a (logarithmically) completely monotonic function. Finally, as applications of the integral representation, in the form of remarks, several integral formulas for a kind of improper integrals are derived, an alternative proof of the famous inequality between the weighted arithmetic and geometric means is supplied, and two explicit formulas for the large Schröder numbers are discovered.     

A Note on Maximum Variance of Order Statistics from Symmetric Populations

The maximum variance of order statistics from a symmetrical parent population is obtained in terms of the population variance. The proof is based on a suitable representation for the variance of order statistics in terms of the parent distribution function.     

Partial Regularity for Higher Dimensional Landau-Lifshitz Systems

1 Initial Value Problem Let M be a m-dimensional compact,smooth,Riemannian manifold without boundary.Forsimplicity,we shall assume M=R~m in our proof since the general case can be handled in thesimilar manner. Consider the Landau-Lifshitz system     

Decomposition techniques for the ocean wave identification problem

This paper deals with the solution of the ocean wave identification problem by means of decomposition techniques. A discrete formulation is assumed. An ocean test structure is considered, and wave elevation and velocities are assumed to be measured with a number of sensors. Within the frame of linear wave theory, a Fourier series model is chosen for the wave elevation and velocities. Then, the following problem is posed (Problem P): Find the amplitudes of the various wave components of specified frequency and direction, so that the assumed model of wave elevation and velocities provides the best fit to the measured data. Here, the term best fit is employed in the least-square sense over a given time interval.Problem P is numerically difficult because of its large size 2MN, whereM is the number of frequencies andN is the number of directions. Therefore, both the CPU time and the memory requirements are considerable (Refs. 7–12).In order to offset the above difficulties, decomposition techniques are employed in order to replace the solution of Problem P with the sequential solution of two groups of smaller subproblems. The first group (Problem F) involvesS subproblems, having size 2M, whereS is the number of sensors andM is the number of frequencies; theseS subproblems are least-square problems in the frequency domain. The second group (Problem D) involvesM subproblems, having size 2N, whereM is the number of frequencies andN is the number of directions; theseM subproblems are least-square problems in the direction domain.In the resulting algorithm, called the discrete formulation decomposition algorithm (DFDA, Ref. 2), the linear equations are solved with the help of the Householder transformation in both the frequency domain and the direction domain. By contrast, in the continuous formulation decomposition algorithm (CFDA, Ref. 1), the linear equations are solved with Gaussian elimination in the frequency domain and with the help of the Householder transformation in the direction domain.Mathematically speaking, there are three cases in which the solution of the decomposed problem and the solution of the original, undecomposed problem are identical: (a) the case where the number of sensors equals the number of directions; (b) the case where Problem P is characterized by a vanishing value of the functional being minimized; and (c) the case where the wave component periods are harmonically related to the sampling time.Numerical experiments concerning the OTS platform and the Hondo-A platform show that the decomposed scheme is considerably superior to the undecomposed scheme; that the discrete formulation is considerably superior to the continuous formulation; and that the accuracy can be improved by proper selection of the sampling time as well as by proper choice of the number and the location of the sensors. In particular, the choice of the sensor location for the Hondo-A platform is discussed.This work was supported by Exxon Production Research Company, Houston, Texas. This paper is based on Refs. 1–6 and is a continuation of the work presented in Refs. 7–12.     

An Approach to the Subproblem of the Cutting Angle Method of Global Optimization

The solution of the Subproblem of the Cutting Angle Method of Global Optimization for problems of minimizing increasing positively homogeneous of degree one functions is proved to be NP-Complete. For the proof of this fact we formulate another problem which we call “Dominating Subset with Minimal Weight”. This problem is also NP-Complete. An O(n²)-time algorithm is presented for approximate solution of Dominant Subset with Minimal Weight Problem. This problem can be expressed as a kind of Assignment Problem in which it is allowed to assign multiple tasks to a single processor. Experimental analysis of the algorithm is performed using the program implemented in ANSI-C. The results of the analysis show the efficiency of the proposed algorithm.Mathematics Subject Classification (2000): 65K05, 90C27, 68Q25     

A Quantum Dynamical Approach to Matrix Khrushchev's Formulas

Khrushchev's formula is the cornerstone of the so‐called Khrushchev theory, a body of results which has revolutionized the theory of orthogonal polynomials on the unit circle. This formula can be understood as a factorization of the Schur function for an orthogonal polynomial modification of a measure on the unit circle. No such formula is known in the case of matrix‐valued measures. This constitutes the main obstacle to generalize Khrushchev theory to the matrix‐valued setting, which we overcome in this paper. It was recently discovered that orthogonal polynomials on the unit circle and their matrix‐valued versions play a significant role in the study of quantum walks, the quantum mechanical analogue of random walks. In particular, Schur functions turn out to be the mathematical tool which best codify the return properties of a discrete time quantum system, a topic in which Khrushchev's formula has profound and surprising implications. We will show that this connection between Schur functions and quantum walks is behind a simple proof of Khrushchev's formula via “quantum” diagrammatic techniques for CMV matrices. This does not merely give a quantum meaning to a known mathematical result, since the diagrammatic proof also works for matrix‐valued measures. Actually, this path‐counting approach is so fruitful that it provides different matrix generalizations of Khrushchev's formula, some of them new even in the case of scalar measures. Furthermore, the path‐counting approach allows us to identify the properties of CMV matrices which are responsible for Khrushchev's formula. On the one hand, this helps to formalize and unify the diagrammatic proofs using simple operator theory tools. On the other hand, this is the origin of our main result which extends Khrushchev's formula beyond the CMV case, as a factorization rule for Schur functions related to general unitary operators.© 2016 Wiley Periodicals, Inc.     

A constructive proof of the Peter‐Weyl theorem

We present a new and constructive proof of the Peter‐Weyl theorem on the representations of compact groups. We use the Gelfand representation theorem for commutative C*‐algebras to give a proof which may be seen as a direct generalization of Burnside's algorithm [3]. This algorithm computes the characters of a finite group. We use this proof as a basis for a constructive proof in the style of Bishop. In fact, the present theory of compact groups may be seen as a natural continuation in the line of Bishop's work on locally compact, but Abelian, groups [2]. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

A note on generating finer‐grain parallelism in a representation tree

The representation tree lies at the heart of the algorithm of Multiple Relatively Robust Representations for computing orthogonal eigenvectors of a symmetric tridiagonal matrix without Gram–Schmidt. A representation tree describes the incremental shift relations between relatively robust representations of eigenvalue clusters of an unreduced tridiagonal matrix, which are needed to strongly separate close eigenvalues in the relative sense. At the bottom of the representation tree, each leaf defines a relatively isolated eigenvalue to high relative accuracy. The shape of the representation tree plays a pivotal role for complexity and available parallelism: a deeper tree consisting of multiple levels of nodes involves tasks associated to more work (i.e., eigenvalue refinement to resolve eigenvalue clusters) and less parallelism (i.e., a longer critical path as well as potential data movement and synchronization). An embarrassingly parallel, ideal tree on the other hand consists of a root and leaves only. As highly parallel hybrid graphics processing unit/multicore platforms with large memory now become available as commodity platforms, exploiting parallelism in traditional algorithms becomes key to modernizing the components of standard software libraries such as LAPACK. This paper focuses on LAPACK's Multiple Relatively Robust Representations algorithm and investigates the critical case where a representation tree contains a long sequential chain of large (fat) nodes that hamper parallelism. This key problem needs to be addressed as it concerns all sorts of computing environments, distributed computing, symmetric multiprocessor, as well as hybrid graphics processing unit/multicore architectures. We present an improved representation tree that often offers a significantly shorter critical path and finer computational granularity of smaller tasks that are easier to schedule. In a study of selected synthetic and application matrices, we show that an average 75% reduction in the length of the critical path and 82% reduction in task granularity can be achieved. Copyright © 2011 John Wiley & Sons, Ltd.     

Approximating the balanced minimum evolution problem

We prove a strong inapproximability result for the Balanced Minimum Evolution Problem. Our proof also implies that the problem remains NP-hard even when restricted to metric instances. Furthermore, we give a MST-based 2-approximation algorithm for the problem for such instances.     

Looping of the numbers game and the alcoved hypercube

We study the so-called looping case of Mozes?s game of numbers, which concerns the (finite) orbits in the reflection representation of affine Weyl groups situated on the boundary of the Tits cone. We give a simple proof that all configurations in the orbit are obtainable from each other by playing the numbers game, and give a strategy for going from one configuration to another. This strategy gives rise to a partition of the finite Weyl group into finitely many graded posets, one for each extending vertex of the associated extended Dynkin diagram. These posets are self-dual and mutually isomorphic, and their Hasse diagrams are dual to the triangulation of the unit hypercube by reflecting hyperplanes. Unlike the weak and Bruhat orders, the top degree is cubic in the number of vertices of the graph. We explicitly compute the rank generating function of the poset.     

Argumentation and algebraic proof

This paper concerns a study analysing cognitive continuities and distances between argumentation supporting a conjecture and its algebraic proof, when solving open problems involving properties of numbers. The aim of this paper is to show that, unlike the geometrical case, the structural distance between argumentation and proof (from an abductive argumentation to a deductive proof) is not one of the possible difficulties met by students in solving such problems. On the contrary, since algebraic proof is characterized by a strong deductive structure, abductive steps in the argumentation activity can be useful in linking the meaning of the letters used in the algebraic proof with numbers used in the argumentation. The analysis of continuities and distances between argumentation and proof is based on the use of Toulmin’s model combined with ck¢ model.     

COMPUTING THE NEAREST BISYMMETRIC POSITIVE SEMIDEFINITE MATRIX UNDER THE SPECTRAL RESTRICTION

Let A and C denote real n × n matrices. Given real n-vectors x1, ... ,xm, m ≤ n, and a set of numbers L = {λ1,λ2,... ,λm}. We describe (I) the set (?) of all real n × n bisymmetric positive seidefinite matrices A such that Axi is the "best" approximate to λixi, i = 1,2,...,m in Frobenius norm and (II) the Y in set (?) which minimize Frobenius norm of ||C - Y||.An existence theorem of the solutions for Problem I and Problem II is given and the general expression of solutions for Problem I is derived. Some sufficient conditions under which Problem I and Problem II have an explicit solution is provided. A numerical algorithm of the solution for Problem II has been presented.     

Mathematics Majors' Perceptions of Conviction,Validity, and Proof

In this paper, 28 mathematics majors who completed a transition-to-proof course were given 10 mathematical arguments. For each argument, they were asked to judge how convincing they found the argument and whether they thought the argument constituted a mathematical proof. The key findings from this data were (a) most participants did not find the empirical argument in the study to be convincing or to meet the standards of proof, (b) the majority of participants found a diagrammatic argument to be both convincing and a proof, (c) participants evaluated deductive arguments not by their form but by their content, but (d) participants often judged invalid deductive arguments to be convincing proofs because they did not recognize their logical flaws. These findings suggest improving undergraduates' comprehension of mathematical arguments does not depend on making undergraduates aware of the limitations of empirical arguments but instead on improving the ways in which they process the arguments that they read.     

On the Kronecker Problem and related problems of Linear Algebra

We consider some classification problems of Linear Algebra related closely to the classical Kronecker Problem on pairs of linear maps between two finite-dimensional vector spaces. As shown by Djokovi? and Sergeichuk, the Kronecker’s solution is extended to the cases of pairs of semilinear maps and (more generally) pseudolinear bundles respectively. Our objective is to deal with the semilinear case of the Kronecker Problem, especially with its applications. It is given a new short solution both to this case and to its contragredient variant. The biquadratic matrix problem is investigated and reduced in the homogeneous case (in characteristic ≠2) to the semilinear Kronecker Problem. The integer matrix sequence Θ_n and Θ-transformation of polynomials are introduced and studied to get a simplified canonical form of indecomposables for the mentioned homogeneous problem. Some applications to the representation theory of posets with additional structures are presented.     

Metaheuristics for the team orienteering problem

The Team Orienteering Problem (TOP) is the generalization to the case of multiple tours of the Orienteering Problem, known also as Selective Traveling Salesman Problem. A set of potential customers is available and a profit is collected from the visit to each customer. A fleet of vehicles is available to visit the customers, within a given time limit. The profit of a customer can be collected by one vehicle at most. The objective is to identify the customers which maximize the total collected profit while satisfying the given time limit for each vehicle. We propose two variants of a generalized tabu search algorithm and a variable neighborhood search algorithm for the solution of the TOP and show that each of these algorithms beats the already known heuristics. Computational experiments are made on standard instances.     

A Branch-and-Cut algorithm for graph coloring

In this paper a Branch-and-Cut algorithm, based on a formulation previously introduced by us, is proposed for the Graph Coloring Problem. Since colors are indistinguishable in graph coloring, there may typically exist many different symmetrical colorings associated with a same number of colors. If solutions to an integer programming model of the problem exhibit that property, the Branch-and-Cut method tends to behave poorly even for small size graph coloring instances. Our model avoids, to certain extent, that bottleneck. Computational experience indicates that the results we obtain improve, in most cases, on those given by the well-known exact solution graph coloring algorithm Dsatur.     

THREE PROBLEMS IN SEARCHING FOR A MOVING TARGET BETWEEN TWO SITES

Suppose that a moving target moves randomly between two sites and its movement is modeled by a homogeneous Markov chain.We consider three classical problems:(1)what kind of strategies are valid(2) what strategy is the optimal(3) what is the infimum of expected numbers of looks needed to detect the target Problem(3) is thoroughly solved,and some partial solutions to problems(1) and(2) are achieved.     

The Roberts characterization of proper and unit interval graphs

In this note, a constructive proof that the classes of proper interval graphs and unit interval graphs coincide is given, a result originally established by Fred S. Roberts. Additionally, the proof yields a linear-time and space algorithm to compute a unit interval representation, given a proper interval graph as input.