Markov chains, R-trivial monoids and representation theory

We develop a general theory of Markov chains realizable as random walks on R-trivial monoids. It provides explicit and simple formulas for the eigenvalues of the transition matrix, for multiplicities of the eigenvalues via Mobius inversion along a lattice, a condition for diagonalizability of the transition matrix and some techniques for bounding the mixing time. In addition, we discuss several examples, such as Toom-Tsetlin models, an exchange walk for finite Coxeter groups, as well as examples previously studied by the authors, such as nonabelian sandpile models and the promotion Markov chain on posets. Many of these examples can be viewed as random walks on quotients of free tree monoids, a new class of monoids whose combinatorics we develop.

Bounds on isoperimetric values of trees

Let G = (V, E) be a finite, simple and undirected graph. For S subset of V, let delta(S, G) = {(u, v) is an element of E : u is an element of S and v is an element of V - S} be the edge boundary of S. Given an integer i, 1 <= i <= vertical bar V vertical bar, let the edge isoperimetric value of G at i be defined as b(e)(i, G) = min(S subset of V:vertical bar S vertical bar=i)vertical bar delta(S, G)vertical bar. The edge isoperimetric peak of G is defined as b(e)(G) = max(1 <= j <=vertical bar V vertical bar)b(e)(j, G). Let b(v)(G) denote the vertex isoperimetric peak defined in a corresponding way. The problem of determining a lower bound for the vertex isoperimetric peak in complete t-ary trees was recently considered in [Y. Otachi, K. Yamazaki, A lower bound for the vertex boundary-width of complete k-ary trees, Discrete Mathematics, in press (doi: 10.1016/j.disc.2007.05.014)]. In this paper we provide bounds which improve those in the above cited paper. Our results can be generalized to arbitrary (rooted) trees. The depth d of a tree is the number of nodes on the longest path starting from the root and ending at a leaf. In this paper we show that for a complete binary tree of depth d (denoted as T-d(2)), c(1)d <= b(e) (T-d(2)) <= d and c(2)d <= b(v)(T-d(2)) <= d where c(1), c(2) are constants. For a complete t-ary tree of depth d (denoted as T-d(t)) and d >= c log t where c is a constant, we show that c(1)root td <= b(e)(T-d(t)) <= td and c(2)d/root t <= b(v) (T-d(t)) <= d where c(1), c(2) are constants. At the heart of our proof we have the following theorem which works for an arbitrary rooted tree and not just for a complete t-ary tree. Let T = (V, E, r) be a finite, connected and rooted tree - the root being the vertex r. Define a weight function w : V -> N where the weight w(u) of a vertex u is the number of its successors (including itself) and let the weight index eta(T) be defined as the number of distinct weights in the tree, i.e eta(T) vertical bar{w(u) : u is an element of V}vertical bar. For a positive integer k, let l(k) = vertical bar{i is an element of N : 1 <= i <= vertical bar V vertical bar, b(e)(i, G) <= k}vertical bar. We show that l(k) <= 2(2 eta+k k)

Embedding Of Non-Simple Lie-Groups, Coupling-Constant Relations And Non-Uniqueness Of Models Of Unification

A general derivation of the coupling constant relations which result on embedding a non-simple group like SU L (2) @ U(1) in a larger simple group (or graded Lie group) is given. It is shown that such relations depend only on the requirement (i) that the multiplet of vector fields form an irreducible representation of the unifying algebra and (ii) the transformation properties of the fermions under SU L (2). This point is illustrated in two ways, one by constructing two different unification groups containing the same fermions and therefore have same Weinberg angle; the other by putting different SU L (2) structures on the same fermions and consequently have different Weinberg angles. In particular the value sin~0=3/8 is characteristic of the sequential doublet models or models which invoke a large number of additional leptons like E 6, while addition of extra charged fermion singlets can reduce the value of sin ~ 0 to 1/4. We point out that at the present time the models of grand unification are far from unique.

Identification of amino groups in the carbohydrate binding activity of winged bean acidic agglutinin

Chemical modification studies reveal that the modification of amino groups in WBA II leads to a complete loss in the hemagglutinating and saccharide binding activities. Since WBA II is a dimeric molecule and contains two binding sites, one amino group in each of the binding sites is inferred to be essential for its activity. The presence of amino group which has a potential to form hydrogen bonded interactions with the ligand, substantiates our observation regarding the forces involved in WBA II-receptor and WBA II-simple sugar interactions.

Convenient construction of tetrahedral finite elements for the quasi-harmonic equation

It is shown that in the finite-element formulation of the general quasi-harmonic equation using tetrahedral elements, for every member of the element family there exists just one numerical universal matrix indpendent of the size, shape and material properties of the element. Thus the element matrix is conveniently constructed by manipulating this single matrix along with a set of reverse sequence codes at the same time accounting for the size, shape and material properties in a simple manner.

Review of continuum, finite element and hybrid techniques in the analysis of stress concentrations in structures

When a uniform flow of any nature is interrupted, the readjustment of the flow results in concentrations and rare-factions, so that the peak value of the flow parameter will be higher than that which an elementary computation would suggest. When stress flow in a structure is interrupted, there are stress concentrations. These are generally localized and often large, in relation to the values indicated by simple equilibrium calculations. With the advent of the industrial revolution, dynamic and repeated loading of materials had become commonplace in engine parts and fast moving vehicles of locomotion. This led to serious fatigue failures arising from stress concentrations. Also, many metal forming processes, fabrication techniques and weak-link type safety systems benefit substantially from the intelligent use or avoidance, as appropriate, of stress concentrations. As a result, in the last 80 years, the study and and evaluation of stress concentrations has been a primary objective in the study of solid mechanics. Exact mathematical analysis of stress concentrations in finite bodies presents considerable difficulty for all but a few problems of infinite fields, concentric annuli and the like, treated under the presumption of small deformation, linear elasticity. A whole series of techniques have been developed to deal with different classes of shapes and domains, causes and sources of concentration, material behaviour, phenomenological formulation, etc. These include real and complex functions, conformal mapping, transform techniques, integral equations, finite differences and relaxation, and, more recently, the finite element methods. With the advent of large high speed computers, development of finite element concepts and a good understanding of functional analysis, it is now, in principle, possible to obtain with economy satisfactory solutions to a whole range of concentration problems by intelligently combining theory and computer application. An example is the hybridization of continuum concepts with computer based finite element formulations. This new situation also makes possible a more direct approach to the problem of design which is the primary purpose of most engineering analyses. The trend would appear to be clear: the computer will shape the theory, analysis and design.

Domains in complex surfaces with non-compact automorphism groups

Let X be an arbitrary complex surface and D a domain in X that has a non-compact group of holomorphic automorphisms. A characterization of those domains D that admit a smooth, weakly pseudoconvex, finite type boundary orbit accumulation point is obtained.

Linear time algorithms for Abelian group isomorphism and related problems

We consider the problem of determining if two finite groups are isomorphic. The groups are assumed to be represented by their multiplication tables. We present an O(n) algorithm that determines if two Abelian groups with n elements each are isomorphic. This improves upon the previous upper bound of O(n log n) [Narayan Vikas, An O(n) algorithm for Abelian p-group isomorphism and an O(n log n) algorithm for Abelian group isomorphism, J. Comput. System Sci. 53 (1996) 1-9] known for this problem. We solve a more general problem of computing the orders of all the elements of any group (not necessarily Abelian) of size n in O(n) time. Our algorithm for isomorphism testing of Abelian groups follows from this result. We use the property that our order finding algorithm works for any group to design a simple O(n) algorithm for testing whether a group of size n, described by its multiplication table, is nilpotent. We also give an O(n) algorithm for determining if a group of size n, described by its multiplication table, is Abelian. (C) 2007 Elsevier Inc. All rights reserved.

A Simple Instrumentation Calibration Technique for Electrical Impedance Tomography (EIT) Using A 16-Electrode Phantom

A simple analog instrumentation for Electrical Impedance Tomography is developed and calibrated using the practical phantoms. A constant current injector consisting of a modified Howland voltage controlled current source fed by a voltage controlled oscillator is developed to inject a constant current to the phantom boundary. An instrumentation amplifier, 50 Hz notch filter and a narrow band pass filter are developed and used for signal conditioning. Practical biological phantoms are developed and the forward problem is studied to calibrate the EIT-instrumentation. An array of sixteen stainless steel electrodes is developed and placed inside the phantom tank filled with KCl solution. 1 mA, 50 kHz sinusoidal current is injected at the phantom boundary using adjacent current injection protocol. The differential potentials developed at the voltage electrodes are measured for sixteen current injections. Differential voltage signal is passed through an instrumentation amplifier and a filtering block and measured by a digital multimeter. A forward solver is developed using Finite Element Method in MATLAB7.0 for solving the EIT governing equation. Differential potentials are numerically calculated using the forward solver with a simulated current and bathing solution conductivity. Measured potential data is compared with the differential potentials calculated for calibrating the instrumentation to acquire the voltage data suitable for better image reconstruction.

Cubic and ultimate groups of complete symmetry

It is shown that the systems of definite actions described by polar and axial tensors of the second rank and their combinations during the superposition of their elements of complete symmetry with the elements of complete symmetry of the "grey" cube, result in 11 cubic crystallographical groups of complete symmetry. There are 35 ultimate groups (i.e., the groups having the axes of symmetry of infinite order) in complete symmetry of finite figures. 14 out of these groups are ultimate groups of symmetry of polar and axial tensors of the second rank and 24 are new groups. All these 24 ultimate groups are conventional groups since they cannot be presented by certain finite figures possessing the axes of symmetry {Mathematical expression}. Geometrical interpretation for some of the groups of complete symmetry is given. The connection between complete symmetry and physical properties of the crystals (electrical, magnetic and optical) is shown.

Nonadiabatic charge pumping by oscillating potentials in one dimension: Results for infinite system and finite ring

We study charge pumping when a combination of static potentials and potentials oscillating with a time period T is applied in a one-dimensional system of noninteracting electrons. We consider both an infinite system using the Dirac equation in the continuum approximation and a periodic ring with a finite number of sites using the tight-binding model. The infinite system is taken to be coupled to reservoirs on the two sides which are at the same chemical potential and temperature. We consider a model in which oscillating potentials help the electrons to access a transmission resonance produced by the static potentials and show that nonadiabatic pumping violates the simple sin phi rule which is obeyed by adiabatic two-site pumping. For the ring, we do not introduce any reservoirs, and we present a method for calculating the current averaged over an infinite time using the time evolution operator U(T) assuming a purely Hamiltonian evolution. We analytically show that the averaged current is zero if the Hamiltonian is real and time-reversal invariant. Numerical studies indicate another interesting result, namely, that the integrated current is zero for any time dependence of the potential if it is applied to only one site. Finally we study the effects of pumping at two sites on a ring at resonant and nonresonant frequencies, and show that the pumped current has different dependences on the pumping amplitude in the two cases.

Time-domain-finite-wave analysis of the engine exhaust system by means of the stationary-frame method of characteristics. Part I. Theory

Time-domain-finite-wave analysis of the engine exhaust system is usually done using the method of characteristics. This makes use of either the moving frame method, or the stationary frame method. The stationary frame method is more convenient than its counterpart inasmuch as it avoids the tedium of graphical computations. In this paper (part I), the stationary-frame computational scheme along with the boundary conditions has been implemented. The analysis of a uniform tube, cavity-pipe junction including the engine and the radiation ends, and also the simple area discontinuities has been presented. The analysis has been done accounting for wall friction and heat-transfer for a one-dimensional unsteady flow. In the process, a few inconsistencies in the formulations reported in the literature have been pointed out and corrected. In the accompanying paper (part II) results obtained from the simulation are shown to be in good agreement with the experimental observations.

On the performance of strain smoothing for quadratic and enriched finite element approximations (XFEM/GFEM/PUFEM)

By using the strain smoothing technique proposed by Chen et al. (Comput. Mech. 2000; 25: 137-156) for meshless methods in the context of the finite element method (FEM), Liu et al. (Comput. Mech. 2007; 39(6): 859-877) developed the Smoothed FEM (SFEM). Although the SFEM is not yet well understood mathematically, numerical experiments point to potentially useful features of this particularly simple modification of the FEM. To date, the SFEM has only been investigated for bilinear and Wachspress approximations and is limited to linear reproducing conditions. The goal of this paper is to extend the strain smoothing to higher order elements and to investigate numerically in which condition strain smoothing is beneficial to accuracy and convergence of enriched finite element approximations. We focus on three widely used enrichment schemes, namely: (a) weak discontinuities; (b) strong discontinuities; (c) near-tip linear elastic fracture mechanics functions. The main conclusion is that strain smoothing in enriched approximation is only beneficial when the enrichment functions are polynomial (cases (a) and (b)), but that non-polynomial enrichment of type (c) lead to inferior methods compared to the standard enriched FEM (e.g. XFEM). Copyright (C) 2011 John Wiley & Sons, Ltd.

Use of finite wordlength FIR digital filter structures with improved magnitude and phase characteristics for reduction of muscle noise in EEG signals

One of the main disturbances in EEG signals is EMG artefacts generated by muscle movements. In the paper, the use of a linear phase FIR digital low-pass filter with finite wordlength precision coefficients is proposed, designed using the compensation procedure, to minimise EMG artefacts in contaminated EEG signals. To make the filtering more effective, different structures are used, i.e. cascading, twicing and sharpening (apart from simple low-pass filtering) of the designed FIR filter Modifications are proposed to twicing and sharpening structures to regain the linear phase characteristics that are lost in conventional twicing and sharpening operations. The efficacy of all these transformed filters in minimising EMG artefacts is studied, using SNR improvements as a performance measure for simulated signals. Time plots of the signals are also compared. Studies show that the modified sharpening structure is superior in performance to all other proposed methods. These algorithms have also been applied to real or recorded EMG-contaminated EEG signal. Comparison of time plots, and also the output SNR, show that the proposed modified sharpened structure works better in minimising EMG artefacts compared with other methods considered.

Stability and throughput analysis of unslotted CDMA-ALOHA with finite number of users and code sharing

We consider a system comprising a finite number of nodes, with infinite packet buffers, that use unslotted ALOHA with Code Division Multiple Access (CDMA) to share a channel for transmitting packetised data. We propose a simple model for packet transmission and retransmission at each node, and show that saturation throughput in this model yields a sufficient condition for the stability of the packet buffers; we interpret this as the capacity of the access method. We calculate and compare the capacities of CDMA-ALOHA (with and without code sharing) and TDMA-ALOHA; we also consider carrier sensing and collision detection versions of these protocols. In each case, saturation throughput can be obtained via analysis pf a continuous time Markov chain. Our results show how saturation throughput degrades with code-sharing. Finally, we also present some simulation results for mean packet delay. Our work is motivated by optical CDMA in which "chips" can be optically generated, and hence the achievable chip rate can exceed the achievable TDMA bit rate which is limited by electronics. Code sharing may be useful in the optical CDMA context as it reduces the number of optical correlators at the receivers. Our throughput results help to quantify by how much the CDMA chip rate should exceed the TDMA bit rate so that CDMA-ALOHA yields better capacity than TDMA-ALOHA.