A Basis of Bideterminants for the Coordinate Ring of the Orthogonal Group

We give a basis of bideterminants for the coordinate ring K[O(n)] of the orthogonal group O(n,K), where K is an infinite field of characteristic not 2. The bideterminants are indexed by pairs of Young tableaux which are O(n)-standard in the sense of King–Welsh. We also give an explicit filtration of K[O(n)] as an O(n,K)-bimodule, whose factors are isomorphic to the tensor product of orthogonal analogs of left and right Schur modules.     

Regularization of diffusion tensor MRI via local coordinates

We propose a novel framework for regularization of symmetric positive-definite (SPD) tensors (e.g., diffusion tensors). This framework is based on differential geometry. The space of SPD matrices, P_n, is described as a Riemannian manifold that is parameterized via the Iwasawa coordinate system. Then, distances on P_n are measured in terms of a natural GL (n)-invariant Riemannian metric. Using the Beltrami framework we construct a set of coupled geometric PDEs with respect to the Iwasawa coordinates. Then, by means of the gradient descent method these equations define the regularization flow over P_n. It appears to be that the local coordinate approach via that coordinate system results in very simple numerics that leads to fast convergence of the algorithm. We demonstrate the efficiency of this algorithm on real volumetric DTI datasets. Results of fibers tractography before and afterthe regularization process arepresented. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Unfolding Orthogonal Polyhedra with Quadratic Refinement: The Delta-Unfolding Algorithm

We show that every orthogonal polyhedron homeomorphic to a sphere can be unfolded without overlap while using only polynomially many (orthogonal) cuts. By contrast, the best previous such result used exponentially many cuts. More precisely, given an orthogonal polyhedron with n vertices, the algorithm cuts the polyhedron only where it is met by the grid of coordinate planes passing through the vertices, together with Θ(n ²) additional coordinate planes between every two such grid planes.     

Grid Vertex-Unfolding Orthogonal Polyhedra

An edge-unfolding of a polyhedron is produced by cutting along edges and flattening the faces to a net, a connected planar piece with no overlaps. A grid unfolding allows additional cuts along grid edges induced by coordinate planes passing through every vertex. A vertex-unfolding allows faces in the net to be connected at single vertices, not necessarily along edges. We show that any orthogonal polyhedra of genus zero has a grid vertex-unfolding. (There are orthogonal polyhedra that cannot be vertex-unfolded, so some type of “gridding” of the faces is necessary.) For any orthogonal polyhedron P with n vertices, we describe an algorithm that vertex-unfolds P in O(n ²) time. Enroute to explaining this algorithm, we present a simpler vertex-unfolding algorithm that requires a 3×1×1 refinement of the vertex grid. This is a significant revision of the preliminary version that appeared in [2]. J. O’Rourke’s research was supported by NSF award DUE-0123154.     

Small free vibrations of an infinite cylindrical shell rotating on rollers

Small free vibrations of an infinitely long rotating cylindrical shell being in contact with rigid cylindrical rollers are considered. A system of linear differential equations for the vibrations of such a shell is derived. By using the Fourier transform of the solutions in the circumferential coordinate, a system of algebraic equations for approximately determining the vibration frequencies and mode shapes is obtained. It is shown that, for any number n of uniformly distributed rollers, the approximate values of the first n frequencies and mode shapes can be found explicitly. On the basis of the orthogonal sweep method, an algorithm for numerically solving the boundary value eigenvalue problem describing the vibrations of a rotating shell is developed. Analytical and numerical results are compared. The obtained approximate formulas for frequencies and the numerical algorithm can be used to design centrifugal concentrators for ore enrichment.     

Restriction varieties and geometric branching rules

This paper develops a new method for studying the cohomology of orthogonal flag varieties. Restriction varieties are subvarieties of orthogonal flag varieties defined by rank conditions with respect to (not necessarily isotropic) flags. They interpolate between Schubert varieties in orthogonal flag varieties and the restrictions of general Schubert varieties in ordinary flag varieties. We give a positive, geometric rule for calculating their cohomology classes, obtaining a branching rule for Schubert calculus for the inclusion of the orthogonal flag varieties in Type A flag varieties. Our rule, in addition to being an essential step in finding a Littlewood–Richardson rule, has applications to computing the moment polytopes of the inclusion of SO(n) in SU(n), the asymptotic of the restrictions of representations of SL(n) to SO(n) and the classes of the moduli spaces of rank two vector bundles with fixed odd determinant on hyperelliptic curves. Furthermore, for odd orthogonal flag varieties, we obtain an algorithm for expressing a Schubert cycle in terms of restrictions of Schubert cycles of Type A flag varieties, thereby giving a geometric (though not positive) algorithm for multiplying any two Schubert cycles.     

A Low Complexity Lie Group Method on the Stiefel Manifold

A low complexity Lie group method for numerical integration of ordinary differential equations on the orthogonal Stiefel manifold is presented. Based on the quotient space representation of the Stiefel manifold we provide a representation of the tangent space suitable for Lie group methods. According to this representation a special type of generalized polar coordinates (GPC) is defined and used as a coordinate map. The GPC maps prove to adapt well to the Stiefel manifold. For the n×k matrix representation of the Stiefel manifold the arithmetic complexity of the method presented is of order nk ², and for nk this leads to huge savings in computation time compared to ordinary Lie group methods. Numerical experiments compare the method to a standard Lie group method using the matrix exponential, and conclude that on the examples presented, the methods perform equally on both accuracy and maintaining orthogonality.     

Deadbeat control: A special inverse eigenvalue problem

In this paper we give a numerical method to construct a rankm correctionBF (where then ×m matrixB is known and them ×n matrixF is to be found) to an ×n matrixA, in order to put all the eigenvalues ofA +BF at zero. This problem is known in the control literature as deadbeat control. Our method constructs, in a recursive manner, a unitary transformation yielding a coordinate system in which the matrixF is computed by merely solving a set of linear equations. Moreover, in this coordinate system one easily constructs the minimum norm solution to the problem. The coordinate system is related to the Krylov sequenceA ^–1 B,A ^–2 B,A ^–3 B, .... Partial results of numerical stability are also obtained.Dedicated to Professor Germund Dahlquist: on the occasion of his 60th birthday     

Computing minimum-area rectilinear convex hull and L-shape

We study the problems of computing two non-convex enclosing shapes with the minimum area; the L-shape and the rectilinear convex hull. Given a set of n points in the plane, we find an L-shape enclosing the points or a rectilinear convex hull of the point set with minimum area over all orientations. We show that the minimum enclosing shapes for fixed orientations change combinatorially at most O(n) times while rotating the coordinate system. Based on this, we propose efficient algorithms that compute both shapes with the minimum area over all orientations. The algorithms provide an efficient way of maintaining the set of extremal points, or the staircase, while rotating the coordinate system, and compute both minimum enclosing shapes in O(n²) time and O(n) space. We also show that the time complexity of maintaining the staircase can be improved if we use more space.     

Orthogonal invariants of skew-symmetric matrices

The algebra of invariants of d-tuples of n?×?n skew-symmetric matrices under the action of the orthogonal group by simultaneous conjugation is considered over an infinite field of characteristic different from two. For n?=?3 and d?>?0 a minimal set of generators is established. A homogeneous system of parameters (i.e. an algebraically independent set such that the algebra of invariants is a finitely generated free module over subalgebra generated by this set) is described for n?=?3 and d?>?0, for n?=?4 and d?=?2,?3, for n?=?5 and d?=?2.     

A general construction of nonseparable multivariate orthonormal wavelet bases

The construction of nonseparable and compactly supported orthonormal wavelet bases of L ²(R ⁿ ); n ≥ 2, is still a challenging and an open research problem. In this paper, we provide a special method for the construction of such wavelet bases. The wavelets constructed by this method are dyadic wavelets. Also, we show that our proposed method can be adapted for an eventual construction of multidimensional orthogonal multiwavelet matrix masks, candidates for generating multidimensional multiwavelet bases.      

Latin Squares without Orthogonal Mates

In 1779 Euler proved that for every even n there exists a latin square of order n that has no orthogonal mate, and in 1944 Mann proved that for every n of the form 4k + 1, k ≥ 1, there exists a latin square of order n that has no orthogonal mate. Except for the two smallest cases, n = 3 and n = 7, it is not known whether a latin square of order n = 4k + 3 with no orthogonal mate exists or not. We complete the determination of all n for which there exists a mate-less latin square of order n by proving that, with the exception of n = 3, for all n = 4k + 3 there exists a latin square of order n with no orthogonal mate. We will also show how the methods used in this paper can be applied more generally by deriving several earlier non-orthogonality results.     

Special representations of the groups U(∞, 1) and O(∞, 1) and the associated representations of the current groups U(∞, 1) X and O(∞, 1) X in quasi-poisson spaces

A method for constructing representations of the current groups O(n, 1) ^X and U(n, 1) ^X , n ε ℕ, developed in the previous papers by the authors is generalized to the case of infinite n. This leads to an interesting difference in construction (absent for finite n) between the cases of the orthogonal and unitary groups, which is due to the different character of special representations of the groups of coefficients.     

On the amicability of orthogonal designs

Although it is known that the maximum number of variables in two amicable orthogonal designs of order 2ⁿp, where p is an odd integer, never exceeds 2n+2, not much is known about the existence of amicable orthogonal designs lacking zero entries that have 2n+2 variables in total. In this paper we develop two methods to construct amicable orthogonal designs of order 2ⁿp where p odd, with no zero entries and with the total number of variables equal or nearly equal to 2n+2. In doing so, we make a surprising connection between the two concepts of amicable sets of matrices and an amicable pair of matrices. With the recent discovery of a link between the theory of amicable orthogonal designs and space‐time codes, this paper may have applications in space‐time codes. © 2009 Wiley Periodicals, Inc. J Combin Designs 17: 240‐252, 2009     

On Kernel polynomials and self-perturbation of orthogonal polynomials

Given an orthogonal polynomial system {Q _n (x)} _n=0 ^∞, define another polynomial system by where α _n are complex numbers and t is a positive integer. We find conditions for {P _n (x)} _n=0 ^∞ to be an orthogonal polynomial system. When t=1 and α₁≠0, it turns out that {Q _n (x)} _n=0 ^∞ must be kernel polynomials for {P _n (x)} _n=0 ^∞ for which we study, in detail, the location of zeros and semi-classical character. Received: November 25, 1999; in final form: April 6, 2000?Published online: June 22, 2001     

On Λ(p)-subsets of squares

This paper is a follow up of [B₁]. It is shown that the sequence of squares {n ²|n=1, 2, ...} contains Λ(p)-subsets of “maximal density”, for any givenp>4. The proof is based on the probabilistic method developed in [B₁] and a precise estimate of the Λ(p)-constant for the sequence of squares itself. Analogues of this phenomenon are obtained for other arithmetic sets, such as the sequence ofkth powers {n ^k |n=1, 2, ...} or the sequence of prime numbers. Sections 2 and 3 of the paper are of independent interest to orthogonal system theory.     

Latin squares with restricted transversals

We prove that for all odd m ≥ 3 there exists a latin square of order 3 m that contains an ( m ? 1 ) × m latin subrectangle consisting of entries not in any transversal. We prove that for all even n ≥ 10 there exists a latin square of order n in which there is at least one transversal, but all transversals coincide on a single entry. A corollary is a new proof of the existence of a latin square without an orthogonal mate, for all odd orders n ≥ 11 . Finally, we report on an extensive computational study of transversal‐free entries and sets of disjoint transversals in the latin squares of order n ? 9 . In particular, we count the number of species of each order that possess an orthogonal mate. © 2011 Wiley Periodicals, Inc. J Combin Designs 20:124‐141, 2012     

The orthogonal convex skull problem

We give a combinatorial definition of the notion of a simple orthogonal polygon beingk-concave, wherek is a nonnegative integer. (A polygon is orthogonal if its edges are only horizontal or vertical.) Under this definition an orthogonal polygon which is 0-concave is convex, that is, it is a rectangle, and one that is 1-concave is orthoconvex in the usual sense, and vice versa. Then we consider the problem of computing an orthoconvex orthogonal polygon of maximal area contained in a simple orthogonal polygon. This is the orthogonal version of the potato peeling problem. AnO(n ²) algorithm is presented, which is a substantial improvement over theO(n ⁷) time algorithm for the general problem.The work of the first author was supported under a Natural Sciences and Engineering Research Council of Canada Grant No. A-5692 and the work of the second author was partially supported by NSF Grants Nos. DCR-84-01898 and DCR-84-01633.     

On orthogonal double covers of kn and a conjecture of chung and west

A collection ?? = {G₁, G₂,…,G_n} of spanning subgraphs of K_n is called an orthogonal double cover if (i) every edge of K_n belongs to exactly two of the G_i's and (ii) any two distinct G_i's intersect in exactly one edge. Chung and West conjectured that there exists an orthogonal double cover of K_n, for all n, in which each G_i has maximum degree 2, and proved this result for n in six of the residue classes modulo 12. In another context, Ganter and Gronau showed that for n ≡ 1 mod 3, n ≠ 10, there exists an orthogonal double cover of K_n in which each G_i consists of an isolated vertex and the vertex disjoint union of K₃'s (actually these orthogonal double covers result from the solution of the directed version of the problem, which reduces to the undirected case when the orientation of the arcs is ignored). Clearly the covers of Ganter and Gronau satisfy the Chung-West requirement. In this article, the configurations of Ganter and Gronau are generalized to include the cases n ≡ 0,2 mod 3, and the results are used to provide a unified solution of the Chung-West problem. For n ≠ 5 mod 6, all the spanning subgraphs in the collection ?? are isomorphic to each other; however, this is not the case when n ≡ 5 mod 6. In addition to solving the Chung-West problem, we also go on to show that for n ≡ 2 mod 3 and n > 287, there exists an orthogonal double cover of K_n in which each spanning subgraph G_i consists of the vertex-disjoint union of an isolated vertex, and quadrilateral, and (n?5)/3 triangles. Of the 96 cases with 2 ? n ? 287, 65 cases are resolved and 31 remain open. © 1995 John Wiley & Sons, Inc.