Inefficiency in packing squares with unit squares

It is shown that, in packing a square of side $\text{n +}\text{1}\text{2}$ with unit squares, the wasted space always has area $\text{? n}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$. This answers a question of Erdös and Graham.     

Latin and magic squares

Latin squares have existed for hundreds of years but it wasn’t until rather recently that Latin squares were used in other areas such as statistics, graph theory, coding theory and the generation of random numbers as well as in the design and analysis of experiments. This note describes Latin and diagonal Latin squares, a method of constructing new Latin squares, as well as the construction of magic squares from an orthogonal pair of diagonal Latin squares.     

Partitions in squares

In this paper we study primarily partitions in different squares. A complete characterization of the least number of terms needed in different cases is given. The asymptotic number of partitions in squares and in different squares is deduced by use of numerical results obtained from extensive computer runs. Some other related problems are also discussed.     

Matrices as sums of squares

How many squares are needed to represent elements in a matrix ring? A matrix over a field of characteristic two is a sum of two squares if and only if its trace is a square, otherwise it is not a sum of squares. Any proper matrix over a field of characteristic not two is always a sum of three squares. If the order of a matrix is even the matrix is a sum of two squares, but an odd order matrix which is q times the identity matrix is a sum of two squares if and only ifq is a sum of two squares in the field. Matrices of order 2,3 and 4 over the integers can always be written as the sum of three squares.     

Latin squares with one subsquare

We look at two classes of constructions for Latin squares which have exactly one proper subsquare. The first class includes known squares due to McLeish and to Kotzig and Turgeon, which had not previously been shown to possess unique subsquares. The second class is a new construction called the corrupted product. It uses subsquare‐free squares of orders m and n to build a Latin square of order mn whose only subsquare is one of the two initial squares. We also provide tight bounds on the size of a unique subsquare and a survey of small order examples. Finally, we foreshadow how our squares might be used to create new Latin squares devoid of proper subsquares—so called N_∞ squares. © 2001 John Wiley & Sons, Inc. J Combin Designs 9: 128–146, 2001     

On packing squares with equal squares

The following problem arises in connection with certain multidimensional stock cutting problems:How many nonoverlapping open unit squares may be packed into a large square of side α?Of course, if α is a positive integer, it is trivial to see that α² unit squares can be succesfully packed. However, if α is not an integer, the problem becomes much more complicated. Intuitively, one feels that for $\text{α = N + (}\text{1}\text{100}\text{)}$, say (where N is an integer), one should pack N² unit squares in the obvious way and surrender the uncovered border area (which is about $\text{α}\text{50}$) as unusable waste. After all, how could it help to place the unit squares at all sorts of various skew angles?In this note, we show how it helps. In particular, we prove that we can always keep the amount of uncovered area down to at most proportional to $\text{α}{}^{\mathrm{<mtext>7</mtext><mtext>11</mtext>}}$, which for large α is much less than the linear waste produced by the “natural” packing above.     

Circle fitting by linear and nonlinear least squares

The problem of determining the circle of best fit to a set of points in the plane (or the obvious generalization ton-dimensions) is easily formulated as a nonlinear total least-squares problem which may be solved using a Gauss-Newton minimization algorithm. This straight-forward approach is shown to be inefficient and extremely sensitive to the presence of outliers. An alternative formulation allows the problem to be reduced to a linear least squares problem which is trivially solved. The recommended approach is shown to have the added advantage of being much less sensitive to outliers than the nonlinear least squares approach.This work was completed while the author was visiting the Numerical Optimisation Centre, Hatfield Polytechnic and benefitted from the encouragement and helpful suggestions of Dr. M. C. Bartholomew-Biggs and Professor L. C. W. Dixon.     

Some observations on local least squares

In previous work we introduced a construction to produce biorthogonal multiresolutions from given subdivisions. The approach involved estimating the solution to a least squares problem by means of a number of smaller least squares approximations on local portions of the data. In this work we use a result by Dahlquist, et al. on the method of averages to make observational comparisons between this local least squares estimation and full least squares approximation. We have explored examples in two problem domains: data reduction and data approximation. We observe that, particularly for design matrices with a repetitive pattern of column entries, the least squares solution is often well estimated by local least squares, that the estimation rapidly improves with the size of the local least squares problems, and that the quality of the estimate is largely independent of the size of the full problem. In memory of Germund Dahlquist (1925–2005).AMS subject classification (2000) 93E24     

Counting dissections into integral squares

A squared rectangle is a rectangle dissected into squares. Similarly a rectangled rectangle is a rectangle dissected into rectangles. The classic paper ‘The dissection of rectangles into squares’ of Brooks, Smith, Stone and Tutte described a beautiful connection between squared rectangles and harmonic functions. In this paper we count dissections of a rectangle into a set of integral squares or a set of integral rectangles. Here, some squares and rectangles may have the same size. We introduce a method involving a recurrence relation of large sized matrices to enumerate squared and rectangled rectangles of a given sized rectangle and propose the asymptotic behavior of their growth rates.     

Magic squares with magic inverses

Characteristic polynomials are used to determine when magic squares have magic inverses. A resulting method constructs arbitrary examples of such squares.     

Quarter-regular biembeddings of Latin squares

We apply a recursive construction for biembeddings of Latin squares to produce a new infinite family of biembeddings of cyclic Latin squares of even side having a high degree of symmetry. Reapplication of the construction yields two further classes of biembeddings.     

Exponential curve fitting with least squares

A comparison is made between standard least squares and a weighted least squares technique for exponential data.     

The existence of Room squares

The authors give a condensed proof of the existence of Room squares for positive odd sides except 3 and 5. Some areas of current research on Room squares are also discussed.Aequationes Mathematicae launches a systematic program of expository papers. We will endeavour to publish at least one in every volume.     

A new class of pandiagonal squares

An interesting class of purely pandiagonal, i.e. non-magic, whole number (integer) squares of orders (row/column dimension) of the powers of two which are related to Gray codes and square Karnaugh maps has been identified. Treated as matrices these squares possess just two non-zero eigenvalues. The construction of these squares has been automated by writing Maple® code, which also performs tests on the results. A rather more trivial set of pandiagonal non-magic squares consisting of the monotonically ordered sequence of integers existing for all orders has also been found.     

Correlations whose squares are perspectivities

This article concerns itself with correlations of finite projective planes which enjoy the property that their squares are non-trivial perspectivities of the plane. Existence results are obtained and actual constructions are carried out, along the lines established in the study of polarities.It is shown that planes of non-square order do not admit correlations whose squares are elations. Also, that planes of odd non-square order do not admit correlations whose squares are homologies of odd order, while planes of even non-square order do not admit any correlations whose squares are homologies.In Desarguesian planes, the connection between the correlations that we are interested in and unitary polarities is made apparent. In the process, the first infinite family of correlations with exactly one absolute point is obtained.Finally, in a non-Desarguesian plane, an example is displayed of a correlation whose square is an elation.This research was supported in part by New York Institute of Technology.     

On greedy randomized coordinate descent methods for solving large linear least‐squares problems

For solving large scale linear least‐squares problem by iteration methods, we introduce an effective probability criterion for selecting the working columns from the coefficient matrix and construct a greedy randomized coordinate descent method. It is proved that this method converges to the unique solution of the linear least‐squares problem when its coefficient matrix is of full rank, with the number of rows being no less than the number of columns. Numerical results show that the greedy randomized coordinate descent method is more efficient than the randomized coordinate descent method.     

Two-stage least squares and indirect least squares algorithms for simultaneous equations models

This paper analyzes the solution of simultaneous equations models. Efficient algorithms for the two-stage least squares method using QR-decomposition are developed and studied. The reduction of the execution time when the structure of the matrices in each equation is exploited is analyzed theoretically and experimentally. An efficient algorithm for the indirect least squares method is developed. Some techniques are used to accelerate the solution of the problem: parallel versions for multicore systems, and extensive use of the MKL library, thus obtaining efficient, portable versions of the algorithms.     

Sub-latin squares and incomplete orthogonal arrays

The main result of this paper is that for any pair of orthogonal Latin squares of side k, there will exist for all sufficiently large n a pair of orthogonal Latin squares with the first pair as orthogonal sub-squares. The orthogonal array corresponding to a set of pairwise orthogonal Latin squares, minus the sub-array corresponding to orthogonal sub-squares is called an incomplete orthogonal array; this concept is generalized slightly.     

Multi-latin squares

A multi-latin square of order n and index k is an n×n array of multisets, each of cardinality k, such that each symbol from a fixed set of size n occurs k times in each row and k times in each column. A multi-latin square of index k is also referred to as a k-latin square. A 1-latin square is equivalent to a latin square, so a multi-latin square can be thought of as a generalization of a latin square.In this note we show that any partially filled-in k-latin square of order m embeds in a k-latin square of order n, for each n≥2m, thus generalizing Evans’ Theorem. Exploiting this result, we show that there exist non-separable k-latin squares of order n for each n≥k+2. We also show that for each n≥1, there exists some finite value g(n) such that for all k≥g(n), every k-latin square of order n is separable.We discuss the connection between k-latin squares and related combinatorial objects such as orthogonal arrays, latin parallelepipeds, semi-latin squares and k-latin trades. We also enumerate and classify k-latin squares of small orders.