text:
Dressing with Control:Using integrability to generatedesired solutions to Einstein’s equations

# Dressing with Control: Using integrability to generate desired solutions to Einstein’s equations

Shabnam Beheshti Department of Mathematics
Rutgers, The State University of New Jersey
Piscataway, NJ, USA 08854
Rutgers, The State University of New Jersey
Piscataway, NJ, USA 08854
###### Abstract.

Motivated by integrability of the sine-Gordon equation, we investigate a technique for constructing desired solutions to Einstein’s equations by combining a dressing technique with a control-theory approach. After reviewing classical integrability, we recall two well-known Killing field reductions of Einstein’s equations, unify them using a harmonic map formulation, and state two results on the integrability of the equations and solvability of the dressing system. The resulting algorithm is then combined with an asymptotic analysis to produce constraints on the degrees of freedom arising in the solution-generation mechanism. The approach is carried out explicitly for the Einstein vacuum equations. Applications of the technique to other geometric field theories are also discussed.

## 1. Introduction

Can solutions to the Einstein Equations be “made to order,” i.e., is it possible to construct spacetimes with a prescribed set of asymptotic “observables” (such as total mass and angular momentum) and a prescribed causal and/or singular structure (e.g. number of components of event horizon, or number of ring singularities, etc.), given a specified set of initial parameters? We provide a first step in answering this question by investigating a solution-generation mechanism for integrable harmonic maps, known as the vesture, or dressing method.

The seeds of our discussion, however, are first sowed in sine-Gordon theory. The special class of nonlinear equations to which the sine-Gordon equation belongs is that of classically integrable partial differential equations (PDEs). Even though nonlinear, these PDEs have the property that new solutions can be formed from old ones, in what amounts to a nonlinear generalization of the superposition principle. We exploit this very feature in order to study the Einstein equations. As a consequence, the main thread of this communication can be summarized in the following diagram:

 sine-Gordon⟶chiral fields⟶% Einstein's equations⟶harmonic maps.

We shall first briefly introduce classically integrable PDEs. Then, building on the techniques developed for the sine-Gordon equation, we introduce Einstein’s gravitational equations and put them in a similar context as sine-Gordon, by briefly reviewing both the Zakharov-Belinski and Ernst formulations of the stationary axisymmetric Einstein vacuum equations. We will then realize this same system of PDEs as an axially symmetric harmonic map.

With background established, we place the gravitational field equations in the context of integrability by way of two theorems; informally, the results state that axially symmetric harmonic maps satisfy an integrable system of equations and that new axially symmetric harmonic maps with any number of prescribed singularities can be constructed from a given one. We implement the algorithm afforded by the proofs of these theorems explicitly in the case of the Einstein vacuum and Einstein-Maxwell equations. It is in the final section that we give a partial answer to the question posed at the beginning of this section, namely, by combining a novel asymptotic expansion with the calculated results of the vesture method, we show that, given any real numbers and , it is indeed possible to treat the arbitrary constants of the dressing procedure as control parameters and produce a 1-solitonic harmonic map that, when viewed as a stationary axisymmetric spacetime metric, has total ADM mass equal to and total ADM angular momentum equal to , and is otherwise free of unwanted pathologies (such as a non-zero NUT parameter), in other words, it is a member of the Kerr family of metrics. We conclude by proposing a strategy for generating solutions in more general cases and indicate possible future directions of study.

## 2. Integrability and Inverse Scattering

A nonlinear PDE (or system of PDEs) is said to be classically integrable if there exists an overdetermined linear system, called a Lax system, the compatibility condition of which is precisely the nonlinear PDE111The term integrable has been adopted in various contexts, and is ambiguous in characterizing the features of such an equation (e.g., existence of closed-form solutions by quadrature, possessing infinitely many conservation laws, exhibiting solitonic dynamics, etc.). We shall restrict our attention to those equations which are integrable in the Lax sense.. We describe this in further detail.

Start with a nonlinear evolution equation for . Associate to it a corresponding overdetermined system for an isospectral family of linear differential operators , with -dependent coefficients, whose eigenfunctions satisfy an additional linear evolution equation

 (1) Lψ=λψ,ψt=Bψ,

where is another linear operator with coefficients depending on and its derivatives. Isospectrality implies a compatibility condition between and , namely

 (2) Lt−[B,L]=0.

Under the appropriate choices222It is a long-standing open problem to characterize the PDEs which admit a Lax formulation. of , this equation agrees with the nonlinear PDE of interest, and the operators and are called a Lax Pair for the PDE [28].

###### Example 1.

One of the first equations to be successfully studied in this setting is the Korteweg-de Vries or KdV equation

 (3) ut−6uux+uxxx=0,

first used in modeling shallow water wave dynamics. Defining the operators and , it is easy to verify that the compatibility condition (2) is satisfied if and only if satisfies (3). Notice that in this case the first equation in (1) is simply a classical eigenvalue problem for a linear Schrödinger operator having as potential.

As the above example demonstrates, the operator depends on the unknown , and may indeed be considerably more complicated than , so solving the Lax system (1) may not be a straightforward task, except possibly at . However, the appearance in (1) of time-evolution for the eigenfunction , provides a starting point for the Inverse Scattering Method (ISM), a nonlinear analogue of the Fourier Transform, to be applicable. The three steps of the ISM are depicted in Figure 1 (excerpted from [16]), in which evolution of the scattering data determined by the eigenvalue problem is used to recover a potential from the Cauchy data of the nonlinear PDE of interest.

In the first step, direct scattering refers to finding a matrix relating asymptotic eigenstates at by way of . Note that is a matrix since the asymptotic eigenspaces are multidimensional. This step requires identifying a Lax pair333It also hinges on space being non-compact and one dimensional.. For integrable equations, isospectrality of the operator implies that the time evolution of is linear; consequently, in the second step, the scattering matrix can be found (rightmost arrow). Upon integration of the Gelfand-Levitan-Marchenko equations associated with the system, the third step, inverse scattering, recovers a time-evolved solution to the original nonlinear PDE of interest. Standard techniques are described in [23, 1, 3] and references therein.

For what follows, we will be careful to distinguish between integrability of a PDE (or system of PDEs) and existence of a solution-generating mechanism for that PDE, noting that many of the examples of this discussion will possess both features.

### 2.1. Classical integrability, extended: the sine-Gordon equation

Expanding the scope of classical integrability to address second order evolution equations involves going from scalar linear operators to matrix operators, sometimes at the expense of introducing powers of , the spectral parameter444Although one is no longer considering an eigenvalue problem in the classical sense, is often still called a spectral parameter.. In this case, matrix equations comparable to (1) are given by

 (4) ∂xψ=Uψ,∂tψ=Vψ,

where and are matrix functions depending on . The compatibility or zero-curvature condition corresponding to (2) is

 (5) Ut−Vx+[U,V]=0.

We take a moment to justify use of the phrase “zero-curvature” by describing the geometry afforded by (4) and (5). Observe that (4) can be used to define a connection on a two-dimensional vector bundle over by setting

 (6) ∇∂xψ=(∂x−U)ψ,∇∂tψ=(∂t−V)ψ,

and extending linearly to , for a vector field . In this manner, we may view the two equations in (6) as parallel transport of in the and directions, respectively. It is then straightforward to calculate the curvature of this connection for the basis vector fields to be

 (7) ∇X∇Yψ−∇Y∇Xψ−∇[X,Y]ψ=(Ut−Vx+[U,V])ψ.

Thus, the connection has zero curvature if parallel transport of along any path connecting two points agrees, i.e., precisely if compatibility condition (5) is satisfied.

###### Example 2.

Matrix formulation of the ISM is used to address the integrability of the sine-Gordon equation (in null coordinates)

 (8) uζη=sinu,

first used in the study of mechanical solitons and differential geometry of constant curvature surfaces555Using the transformation , one may easily recover the second recognizable form of the sine-Gordon equation, .. Defining as

the Lax system analogous to (4) is given by , and the zero curvature condition ensures that evolves according to (8). A comparable initial value problem to the one depicted in Figure 1 is explicitly solved for the sine-Gordon equation by the ISM in [2]; full details for the inverse scattering procedure may be found in [47, 48]. It is worth noting that various Lax formulations are possible, by choosing different in (4) (see, for instance, [49]).

### 2.2. From sine-Gordon to Chiral Fields

Progression from matrix Lax pairs for a single nonlinear PDE to matrix Lax pairs for nonlinear systems of PDEs occurs naturally when studying simple geometric field theories, as the next example demonstrates. What is surprising is that from the appropriate perspective, this matrix operator modification applies equally well to equations of gravitation and electrodynamics.

###### Example 3.

Let be an open subset of with coordinates and suppose is a smooth function of with values in a semisimple Lie group . Denote by and consider the following action

 (9) S[g]=∫U12Tr (gζg−1η)dζdη.

The Euler-Lagrange equations of this action are known as equations of the principal chiral field on the group –a free field in two-dimensional spacetime with values in [50, 47, 41]. The word chiral here refers to the fact that this Lagrangian is invariant separately under the left, and the right, action of the group on itself. With a non-commutative group, this action can thus be used to model physical phenomena that appear to break the chiral symmetry, such as the interaction of mesons in the chiral limit [25]. In that case where is the number of quark flavors.

By introducing the compact notation , , and observing that , the Lagrangian density in (9) becomes . Consequently, the field equations are re-expressed as

 (10) Aη−Bζ = 0 Aη+Bζ+[A,B] = 0,

where the second equation is the compatibility condition arising from the definitions of and .

To solve these equations for by means of inverse scattering, we cast (10) as the compatibility condition of a linear system of matrix equations of the form

 (11) ∂ζψ=Uψ,∂ηψ=Vψ,

for a vector function of and matrix functions of and a complex parameter . Equality of mixed partials in imposes the compatibility condition just as in (5), replacing and by and , respectively, yielding

 (12) Uη−Vζ+[U,V]=0.

There are several quantities to determine in (11), with varying degrees of freedom. The matrices are to be determined in terms of and , bearing in mind the compatibility conditions of both and ; furthermore, given a solutions of the linear system, the desired matrix should be recoverable by fixing a value of the parameter , under the definitions of and . Zakharov and Shabat carried out a vesture method (later called the dressing technique) to solve this overdetermined system of conditions by assuming have simple poles in :

 (13) U=U0+N1∑n=1Unλ−λn,V=V0+N2∑n=1Vnλ−μn.

Substituting these expressions into zero-curvature condition (12) and clearing denominators, one obtains a polynomial in of degree , which splits into equations corresponding to coefficients of the polynomial [47, 48].

In the special case , where each have one simple pole the compatibility condition (12) reduces to a degree 2 polynomial in from which three equations are obtained. For instance, assuming and under appropriate assumptions on , (11) can be reduced to a Lax formulation of sine-Gordon equivalent to the one given in Example 2. A complete analysis appears in [49, 21]. Note that just as in the previous examples, (11) naturally defines the covariant differentiation operations given by and .

###### Remark 1.

Under the coordinate transformation , the Lagrangian density of the action (9) differs by a null Lagrangian from , where and . Noting that must lie in the Lie algebra of the Lie group , the transformed action may be viewed as an inner product of the matrix-valued one-form with itself, relative to the Minkowski metric on . As we shall see, this one form can be interpreted as the pull-back of the Maurer-Cartan form under the mapping . We shall also see below that the principal chiral field is simply a harmonic map into a Lie group. These two facts will combine in a particularly elegant manner where the integrability of such maps is studied.

## 3. Gravitational Equations

Motivated by the last example, we turn our attention to the Einstein vacuum equations with vanishing cosmological constant

 (14) Rμν=0,μ,ν=0,…3.

This quasilinear system is satisfied by the metric tensor of a four-dimensional Lorentian manifold . Here, denotes the Ricci curvature tensor of . Complexity of these field equations is reduced considerably using symmetry reductions, corresponding to existence of Killing fields for the metric . In this context, existence of timelike Killing fields correspond to stationary metrics, and existence of spacelike Killing fields correspond to spherically symmetric or axisymmetric metrics (depending on whether the action generated is an or rotation, respectively). Under such symmetries, the simplest nontrivial asymptotically flat solutions666Asymptotically flat solutions represent vacuum outside an isolated body. are Schwarzschild spacetimes, which are static and spherically symmetric, and the Kerr spacetimes, which are stationary and axisymmetric [36, 27].

We shall describe two approaches for the analysis of a two-Killing field reduction of (14), namely the Zakharov-Belinski and the Ernst formulations, and establish a concrete connection between them by way of harmonic maps.

### 3.1. Integrable formulation of the Einstein vacuum equations

First, we briefly outline the techniques in [8, 9] used to establish integrability of the stationary, axisymmetric Einstein vacuum equations. Assuming the existence of two commuting Killing fields, the spacetime metric can be expressed in block-diagonal form

with and [33]. Here the sign is to be used when both Killing fields are spacelike (and hence is Lorentzian), while the sign is for the case of one timelike and one spacelike Killing field (in which case the quotient metric is Riemannian). In the former case, let be null coordinates on the quotient manifold, and in the latter, set . The equations for are given by

 (16) Aη−Bζ = 0 Aη+Bζ+1α[A,B]−αηαA+αζαB = 0,

for , , . Compare with the chiral field model (10). The task is to find a linear system for analogous to (11) for which the above PDE system appears as a compatibility condition; note that once is determined, can be found by quadrature (see, e.g. [43]).

Just as in (4) for the sine-Gordon equation and (11) for the chiral field, assume and have simple poles in . The key idea used in establishing integrability in this case is a generalization of to operators which include differentiation in the spectral parameter , namely

 (17) D1ψ=Uψ:=Aλ−αψ,D2ψ=Vψ:=Bλ+αψ,

where , and is a rational function of . We shall interpret these generalized derivatives geometrically in Section 4. Note that here , thus in contrast to the chiral field model, the poles in (17) are not fixed, but moving.

With integrability established, the authors of [8, 9] implement a vesture or dressing method to generate new solutions to the Einstein vacuum equations. Formally, given a solution of the Lax system having initial data , dressing refers to the procedure of finding a matrix for which also solves the system. It is from this “dressed” generating matrix that new solutions (and hence ) are constructed. Determining the dressing matrix reduces to solving a finite system of algebraic equations. In the next section we shall describe a generalization of this technique in the context of dressing harmonic maps.

### 3.2. Ernst Formulation of the vacuum equations

Prior to the works of [8, 9], another approach to the two-Killing field reduction of EVE had been investigated in [19, 20], giving what is now known as the Ernst Equation for a complex potential function . We briefly review this now.

Let the two commuting Killing fields for the metric be denoted by and . Let us assume that is timelike and spacelike. Set

 (18) X:=−g(K,K)>0, ~X=g(~K,~K), W:=g(K,~K), Ω:=WX,

and define

 (19) ρ:=√W2+X~X,b:=iK∗dK.

Thus, is the element of area of the cylindrical group orbits and is the twist form of . The line element of is then

where is a metric on the two-dimensional Riemannian quotient manifold conformal to .

Suppose now that the metric is a solution of Einstein vacuum equations. It then follows that (i) the function is harmonic , and (ii) is closed, i.e. . Thus (assuming the domain is simply connected) . The function is called the twist potential for the Killing field (see e.g. [43]). Choosing a conjugate harmonic function for , and using as isothermal coordinates on the quotient brings the line element to the form

 (21) ds2g=−X(dt+Ωdφ)2+1X(ρ2dφ2+e2u(dρ2+dz2)).

This is known as the Lewis-Papapetrou form of the metric. There are now only three unknown metric coefficients left: , and . Next, by virtue of and being Killing fields (and the Einstein vacuum equations being satisfied), it is possible to show that the quantities and satisfy a coupled system of elliptic PDEs, which can be combined into a single equation by introducing a complex-valued potential , called the Ernst potential:

 (22) (ε+¯ε)△ε+2∇ε⋅∇ε=0.

Once the potential is found, the remaining metric coefficients and can be found using quadratures [43].

Equation (22) is derivable from a variational principle, namely, it is the Euler-Lagrange equation of the following action

 (23) ∫R21(Rε)2|∇ε|2dx=∫∫14X2(|∇X|2+|∇Y|2)ρdρdz

We will see below that this is also the action for a harmonic map into the hyperbolic plane.

### 3.3. Harmonic Maps and Gravitation

Recall that a harmonic map is a critical point of the Dirichlet Energy

 (24) E[f,D]=∫D12trgf∗h.

This definition generalizes the notion of a geodesic to higher-dimensional domains: letting , the Euler-Lagrange equations for the harmonic map action reduce precisely to the equations of an energy-minimizing geodesic on . Harmonic maps also generalize harmonic functions to nonlinear targets: letting , the Euler-Lagrange equation for (24) corresponds to that of a harmonic function on the base manifold . With this notation in place, we can cast some of our prior examples from the previous sections in the context of harmonic maps777The sine-Gordon equation can also be put into this framework, see [37]..

Example 3, revisited. To express the chiral field appearing in Example 3 as a wave map, the hyperbolic analog of a harmonic map, let with a mapping from the -dimensional Minkowski space into the group , and null coordinates on the domain. The Maurer-Cartan form of is , a Lie-algebra-valued 1-form. Let denote its pull-back under . Thus where is a basis for the Lie algebra of the group , and are 1-forms on the domain: . On the other hand, if is semi-simple, the Killing-Cartan quadratic form is non-degenerate, and it thus endows with a pseudo-Riemannian888The metric is Riemannian if is a compact group. metric . With denoting the Minkowski metric, we thus have

 (25) 12trgf∗h=12gμνκabθaμθbν=12gμνtr(XaXb)θaμθbν=12tr(W2),

which agrees with (9). More precisely, , so that , the chiral field Lagrangian, as before.

We now move on to the reduction of vacuum Einstein equations under the assumption of existence of two commuting Killing fields.

###### Example 4.

Let denote a solution of Einstein’s vacuum equations possessing two commuting Killing fields. We may then express the line element of in the Lewis-Papapetrou form (21). Let be coordinates on the real hyperbolic plane with its standard metric ,

 (26) ds2h=dX2+dY2X2.

Suppose is a harmonic map that is invariant under the action of the two given Killing fields, so that is well-defined on the quotient manifold, . The harmonic map Lagrangian density is therefore

 (27) trgf∗h√−detg = 14X2{gρρ[(∂ρX)2+(∂ρY)2]+gzz[(∂zX)2+(∂zY)2]}ρe2uX = 14X2(|∇X|2+|∇Y|2)ρ

which is the same as (23), the Lagrangian obtained for the Ernst equation. Indeed, since the action is independent of all other features of the spacetime metric, we can pretend that the domain is simply in cylindrical coordinates , and that we have an axisymmetric (i.e. -independent) harmonic map from into the hyperbolic plane.

Finally, observing that the real hyperbolic plane may be realized as a symmetric space , we may use the Cartan embedding of a symmetric space into its mother Lie group , to represent as a mapping into , namely

 (28) (X,Y)→1X(X2+Y2YY1).

The fact that the target of the map is now embedded in a linear space999Note that by virtue of the Cartan embedding, a symmetric space can be embedded into a Lie group, for which one may choose a matrix representation, thus making addition and scalar multiplication of elements possible. is the key to the success of the vesture method, described in the next section.

###### Example 5.

The Einstein-Maxwell system, equations governing the interaction of the spacetime metric with an electromagnetic field , given by

 (29) Rμν−12gμνR=κTμν,Tμν:=Fλμ∗Fνλ−gμνFαβFαβ,dF=0,d∗F=0,

also represent the equations of an axially symmetric harmonic map, assuming existence of two commuting Killing fields which also leave the field invariant. In this case, the mapping is given by , where is as in the previous example, and is the complex hyperbolic plane realized as with , and [20, 11, 29], and the corresponding Ernst formulation now involves a pair of complex potentials [19, 20, 12].

Appearances of harmonic maps in physics have been extensively documented, as has the integrability of harmonic maps into particular targets; see [30, 35, 45], for instance. The primary observation we now make is the following: the chiral field, Einstein vacuum and Einstein-Maxwell equations (under a two-Killing-field reduction) are integrable and admit a dressing mechanism simply because harmonic maps into symmetric spaces are integrable and admit a generalized dressing mechanism.

## 4. Integrability and vesture of axially symmetric harmonic maps

Motivated by previous work, we prove a pair of theorems in [7] which unify the integrability and solution-generating mechanism (vesture or dressing technique) of special cases considered in the literature for the Einstein vacuum, Einstein-Maxwell and Chiral Field models; the results further establish integrability and vesture for a broader class of geometric field theories. We shall outline the main points surrounding their proof, after which the second half of this communication will focus on control of the solution-generating mechanism.

### 4.1. Integrability of axially symmetric harmonic maps

###### Theorem 1.

(Integrability) Let be a real semisimple Lie group and a maximal compact subgroup. Then any axially symmetric harmonic map from into the Riemannian symmetric space satisfies an integrable system of equations.

The proof of this statement involves two main steps. Let where the metric is given in cylindrical coordinates . Suppose is an axially symmetric harmonic map and let be a parametrization of the symmetric space via the Cartan embedding , so that .

Step Rewrite the equations of a harmonic map as a Hodge System. Using the pull-back of the Maurer-Cartan form , the harmonic map equations are

 (30) dW+W∧W=0,d(ρ∗W)=0,

where the domain is the right-half plane in with coordinates .

Step Exhibit a Lax Pair whose compatibility condition is the Hodge System. In our case, we generalize the linear operators appearing in (17) by defining

 (31) DΨ=−ΩΨ,Ψ|λ=0=q,
 Dμ:=∂μ−ωμ∂∂λ,ωμ:=1∂ϖ/∂λ∂μϖ,Ωμ:=aWμ+bρ(∗W)μ,μ=1,2,

where , , and , , are three specific -valued functions on defined to be

 (32) ϖ(λ,x)=ρ22λ+z−λ2,a(λ,x)=ρ2λ2+ρ2,b(λ,x)=λλ2+ρ2.

The unknown is , solving the Lax System (31). Here is the dimension of a regular representation of the Lie group . Note that this treatment subsumes approaches appearing in [8, 9, 5, 18].

###### Remark 2.

We remark that just as in Examples 2, 3, the operator defines a connection on the domain of , a Riemann surface bundle , where is the two-sheeted Riemann surface defined by

 (33) Rx={(λ,ϖ)∈C2 | λ2−2λ(z−ϖ)−ρ2=0}.

The mapping , is a deck transformation on the universal cover of and for all . We prove in [7] that the compatibility condition of the is equivalent to a zero curvature condition , for the 1-form on the domain (cf. [24], p. 54).

### 4.2. Vesture of axially symmetric harmonic maps

###### Theorem 2.

(Vesture) If the Lie group is such that the two involutions and defining the symmetric space can be given by conjugation with the same element, then the vesture method can be used to construct new harmonic maps starting from any given harmonic map.

As stated earlier, vesture refers to the procedure of finding a dressing matrix such that if is a solution of (31) and

 (34) Ψ=χΨ0,

then also solves the Lax system (31). Using the notation set up in Theorem 1, we prove this result in two main steps as well.

Step Construct a dressing matrix possessing the appropriate symmetries. An invertible mapping is a dressing matrix for , an axially symmetric harmonic map of into , if it satisfies

 χ(∞) = I (35) τ(χ(¯¯¯λ)) = χ(λ) χ(λ) = χ(0)q0σ(χ(Tx(λ)))σ(q0).

Here, are commuting involutions characterizing the symmetric space and is a complex group containing [26]; the second and third equations in (4.2) are referred to as the G-reality and involutive symmetry conditions, movitated by the study of wave maps into compact symmetric spaces in [40, 39]. The symmetry conditions in (4.2) ensure that the resulting axially symmetric harmonic map , found by setting in the generating matrix , takes its values in the appropriate target space, . We show that there always exists an element of the equivalence class of which satisfies such imposed symmetries [7].

Step Reduce the problem of finding the dressing matrix to an algebraic problem. Motivated by simplifications appearing in [8, 9, 18], we assume is a rational function of and unknown matrices of the form

 (36) χ(x,λ)=I+2N∑k=1Rk(x)λ−λk(x).

The moving poles, , are specified in the next section. Under further assumptions on the involutions we prove solvability of the linear system in .

We summarize Theorems 1 and 2 in Figure 2. Steps and comprise the integrability component (top arrow) and steps and comprise the vesture component (rightmost and bottom arrows) of the results. Compare with Figure 1. In our case, the dressing procedure results in axisymmetric harmonic maps possessing ring singularities [7].

The linear system resulting from this reduction unfortunately still contains too many unknown (and seemingly free) parameters. Thus, the question posed at the beginning of this paper is restated as: Can we control the output of this mechanism to generate desired harmonic maps from a given initial seed map , and if so, how?

### 4.3. The Dressing Algorithm

In order to control the number of parameters appearing in the dressing mechanism, we will need to outline the solution-generating algorithm afforded by the proof of Theorem 2. We do so now.

Let be distinct non-real complex numbers in the upper half plane. For every , each corresponds to a pair of points on the Riemann surface defined in (33). Number these prescribed poles in such a way that they are related by the deck transformation on :

 (37) λN+k=Tx(λk)=−ρ2λk,1≤k≤N.

Suppose that the involutions characterizing the symmetric space target can be given by conjugation with respect to the same element . In conjunction with the G-reality and involutive symmetry conditions in (4.2), this assumption allows the algebraic reduction to be carried out efficiently101010In particular the pseudo-unitary groups satisfy this assumption. Moreover, groups possessing Dynkin diagrams with no symmetries may also qualify. Modification of this procedure to address other families of involutions will be taken up in a future work..

The overdetermined system in is further simplified using a rank-one assumption. Define , where and assume there exist non-zero vector functions for such that

 (38) Mk=ukv∗k,

and furthermore that the vectors satisfy

 (39) vk=ΓvN+kk=1,…,N.

This rank-one ansatz is consistent with the prior conditions imposed on the system by symmetry, and the relation on the vectors imposes a relation on the vectors which does not overdetermine the problem.

Although the system is equivalent to a nonlinear system for the , it is shown in [7] that can be taken to be constant vectors, and that the rank one assumption reduces the system to a linear system for the unknown vector functions , given by

 (40) ∑jakju∗j=b∗k,akj:=1λk−¯¯¯λjv∗kSkjvj,b∗k:=−v∗kΨ−10kΓ,

where we have set

 (41) Skj:=Ψ−10kΓ(Ψ∗0j)−1=ΓΨ∗0kΓΨ0jΓ.

Thus, a complete set of unknowns for the problem are the vectors , given an arbitrary set of constant vectors in . Equation (40) can be written more compactly in matrix form as

 (42) AU∗=B∗.

Here is the matrix whose columns are the vector functions , is a matrix function, and is the matrix whose columns are the vector functions defined above.

If the matrix can be shown to be invertible (at least in a neighborhood in ), then the above system has a unique solution in that neighborhood. From there, one can then calculate the matrices and the dressing matrix , and setting , the new solution is found to be

 (43) q(x)=q0(x)−2N∑k=11λk(x)uk(x)v∗kΨ−10k(x)q0(x).

In general, is not invertible everywhere in the domain , and indeed the zero set of has a geometric significance for the dressed harmonic map . However, we can prove that under appropriate conditions on the arbitrary vectors , the matrix is, in general, invertible for large (i.e., in a neighborhood of infinity). Once a has been found, its domain of definition may be maximally extended by analytic continuation.

###### Remark 3.

Observe that (40) and hence (43) satisfies scaling invariance: if we rescale the constant vectors by (nonzero) complex constants , , then the expressions for also rescale by a factor of . This suggests that by rescaling each by , one preserves the equality in (43). Thus, we may view not as vectors in , rather as elements of . This also means that the actual number of free real parameters in our dressing procedure is , and not as it initially appeared to be (from arbitrary constant vectors in ). We shall invoke the scale invariance of the system explicitly when it is convenient to do so in our subsequent calculations.

## 5. N-solitonic solutions of Einstein’s Equations

The solution-generating algorithm outlined in the previous section is realized concretely for the case of the pseudo-unitary groups, in [7]. Define involutions on by

 (44)

Then , , and using the Cartan embedding, the symmetric space is the complex Grassmann manifold

 (45) Gp,q:=G/K=SU(p,q)/S(U(p)×U(q))={q∈G | qΓqΓ=I}.

In the special case where , one obtains , the target in the Ernst reduction of Einstein vacuum equations, appearing in Example 4, and for the case , one obtains , the target in the Ernst reduction of Einstein Maxwell equations, appearing in Example 5.

### 5.1. Kerr spacetimes from 1-soliton dressed Minkowski metrics

We now specialize to the case to demonstrate the dressing algorithm explicitly, showing that dressing Minkowski spacetime with one soliton results in a family of (naked) Kerr spacetimes.

1. (Choose initial seed) Recall from Example 4, in the Ernst formulation of the vacuum Einstein equations, , where as a harmonic map, . Thus, the Minkowski spacetime metric can be expressed as the harmonic map into given by

 (46) q0(x)=I2×2:R2+⟶SU(1,1)/S(U(1)×U(1)),

where . We solve the Lax system (31) by inspection and find .

2. (Dress ) Fix , and let be the two roots of so that

 (47) χ(x,λ)=I+R1(x)λ−¯¯¯¯¯λ1+R2(x)λ−¯¯¯¯¯λ2.
3. (Linear Algebra) Set for , so that by (39), . Rewrite , as in (40), in terms of and vectors :

 (48) ⎡⎢ ⎢ ⎢ ⎢⎣1λ1−¯¯¯¯¯λ1(|α|2−|δ|2)1λ1−¯¯¯¯¯λ2(|α|2+|δ|2)1λ2−¯¯¯¯¯λ1(|α|2+|δ|2)1λ2−¯¯¯¯¯λ2(|α|2−|δ|2)⎤⎥ ⎥ ⎥ ⎥⎦⎡⎢⎣u∗1u∗2⎤⎥⎦=[−¯¯¯¯α¯¯¯δ−¯¯¯¯α−¯¯¯δ]=:[c−v∗1−v∗2].

Solving for above, the new harmonic map in (43), expressed in terms of the complex constants and , is given by

 (49) q(x)=χ(x,0)q0(x)=I2×2−1λ1u1(x)v∗1−1λ2u2(x)v∗2.
4. (Change coordinates) We now change from Weyl coordinates to Boyer-Lindquist coordinates , defined as

 (50) ρ=√(r−m)2+s2sinθ,z=(r−m)cosθ,

for real parameters . Then the harmonic map is re-expressed as

 q = ⎛⎜ ⎜ ⎜ ⎜⎝1+8|α|2|δ|2s2F1F[−4sα¯δ(iA(r−m)−Bscosθ)]I2×21F[4s¯αδ(iA(r−m)+Bscosθ)]1+8|α|2|δ|2s2F⎞⎟ ⎟ ⎟ ⎟⎠, (51) A = |α|2−|δ|2,B=|α|2+|δ|2,F=A2((r−m)2+s2)−B2s2sin2θ.

At this point, we would like to systematically deduce whether particular choices of constants lead to recognizable solutions, such as Kerr spacetimes. We use this formulation of the harmonic map to develop our control theory approach.

### 5.2. Control Theory meets GR: an asymptotic calculation

In the solution-generating algorithm, it is necessary to invert the matrix to solve the linear system appearing in (40) and (48) for the unknown vectors . However, for each soliton added into the system, that is, for each , the matrices , and grow in considerably size (order ). The plan will be to replace with coordinates at infinity and write down an asymptotic expansion for in powers of , for which truncations of the matrix will be more readily inverted. This is made possible by that fact that since the roots can be expressed in terms of the elliptical coordinates

 (52) λ1=(r+m+is)(cosθ−1),λ2=(r+m−is)(cosθ+1),

we have as (since as well) for all .

First observe that in the coordinates , the matrix can be expressed as , where is a diagonal matrix and is a nilpotent skew-hermitian matrix, . Consequently,

 (53) A = D+1RN=D(I+1RD−1N) ⇒A−1 = (I+1RD−1N)−1D−1=D−1−1RD−1ND−1+1R2D−1ND−1ND−1−⋯

This, in turn, allows us to deduce constraint equations on the constants by explicitly inverting in (39) using truncations of this expansion. In particular

 (54) U=−BD−1+1RBD−1ND−1−1R2BD−1(ND−1)2+1R3BD−1(ND−1)3−⋯

can be calculated to various desired orders of .

In our example, we shall truncate the expansion of at the term and, recalling the definitions of from (4), we use

 (55)

Calculating explicitly to obtain the column vectors and combining them with the constant row vectors , we compute each component of the new (truncated) mapping . Note that each contains a prefactor of , resulting in the following components for


text:
# QuestionSurfaceTiles / Base Maker for Orbiter 190914 or similar?

#### smewthies

##### New member
Hello,

I used to play this simulator a LOT way back in 2007 for years, and I have been getting more back into it lately.

I've done searching but the relevant threads are years old so maybe outdated information. I downloaded Civilian Airports from orbithangar and I can't get the included textures to show up in the sim. The runways are there but still the basic very low resolution surface tiles. I have placed the included .dds files in their respective folders and even copied them elsewhere to see if anything worked. I first placed them in the main Textures folder as that's how they come, but then I put them in Textures/Earth and Config/Earth and Config/Earth/Base. The surface bases show up on the map module as well, just the textures aren't loading.

Also, this inspires me to want to download my own surface tiles and airports for places I've lived- Cincinnati area, Indianapolis as well as Minnesota. I tried downloading Orbiter Base Maker 2.0.3 but it gives me an "Error Downloading Image" so I'm not sure if it's old/unsupported these days. I don't even care as much about the runways as I know that'll be a lot of work but I mainly want the higher resolution surface textures. I want to see those places in detail and I have the hardest time even finding my current city (Rochester MN) due to the low detail.

Is there a guide somewhere on how to get this done? Like I said I tried searching but maybe didn't know what to search for or didn't use the right keywords.

Thanks a bunch for the help!

Also, I use the D3D9 graphics client but I'm willing to switch that or even go to an older Orbiter version to make this work.

#### Max-Q

##### 99 40
Older o2010 type surface tiles don’t work in o2016. The whole design for planet textures was changed for 2016, There is a PDF about how it works in the orbiter documentation folder. IIRC it includes a section about how to convert 2010 type base tiles.

#### smewthies

##### New member
Oh gosh, I'm going to have a lot of reading to do. Found in /Doc/PlanetTextures.pdf:

Code:
If Earth_2_W0462_N0161.dds was provided as a 256256 texture, then it can't be
directly converted into a quadtree tile. The following options are available:
a) If the appropriate neighbour base textures are present, (in this case,
Earth_2_W0463_N0161.dds,
Earth_2_W0462_N0160.dds,
Earth_2_W0463_N0160.dds
they can be combined into a single 512512 texture and saved as
Earth\Surf\13\000175\000281.dds.
b) The texture can be interpolated to size 512512 using an image editing utility and
then saved as a quadtree tile.
ORBITER Planetary Textures (c) 2000-2016 Martin Schweiger 12
c) The 256256 base tile can be copied into the appropriate quadrant of the original
Earth\Surf\13\000175\000281.dds parent quadtree tile, if it exists.
Note that the base tiles may need to be edited to colour-match the underlying lowerresolution quadtree tiles to provide a seamless transition. Histogram-matching algorithms can be useful here

I can't even figure out tileedit. I'm way in over my head... I feel like it shouldn't be this complicated... there's gotta be an easier way.

#### N_Molson

Donator
It would definitively be cool to have an up-to-date interactive editor.

#### 4throck

##### Enthusiast !
Terrain Tool Box allows you to edit tiles:
terrain-toolkit.37665/#post-561724

It runs from inside Orbiter, and allows you to select the surface you want to export/import as PNG.
So it's a simple save, edit, load job

Of course, in true Orbiter 2016 fashion , it's only a half solution, as it will crash if used with a modern D3D9 version
You need to use D3D9 R4.7 (11 August 2020), but as far as I know, that version is not available.

#### smewthies

##### New member
Terrain Tool Box allows you to edit tiles:
terrain-toolkit.37665/#post-561724

It runs from inside Orbiter, and allows you to select the surface you want to export/import as PNG.
So it's a simple save, edit, load job

Of course, in true Orbiter 2016 fashion , it's only a half solution, as it will crash if used with a modern D3D9 version
You need to use D3D9 R4.7 (11 August 2020), but as far as I know, that version is not available.
Dang and I'm sure I'm SOL for being on the beta as well... even if I go back to the stable 2016, I wish I could just download level 19 surface tiles more than anything else

#### smewthies

##### New member
Hmmm. They link to the required D3D9 client in that thread, but I can't get it to work still. When I click on terrain toolbox in the function menu, nothing happens. This is on Orbiter 2016, fresh install.

#### jacquesmomo

Hi smewthies

Yes, the tile-system is very different from Orbiter 2010 and earlier...

Before, the tiles were visible whatever the altitude, and were declared in the file <your_base>.cfg.

Now the tiles are:
• either in the \Textures\Earth\Archive folder and are *.tree files (kind of archive a bit like a *.zip)
• either (in general these are the "added" or "personalized" tiles) in the \Textures\Earth\Surf folder (and Mask and Elev sub folders)

And these tiles are visible "by successive layers": one layer replaces the other (previous or next) depending on the altitude.
That doesn't make it easy!!!
(It's well explained in the doc you're talking about.)

In this regard, remember to indicate in the launchpad tab "video" then "advanced" and finally set "tile archive" with "Cache & archive" (with D3D9)

Clarification: "old style" tiles can work, declared in the <your_base>.cfg file but not with D3D9.

Just for information :
the "SURF" tiles are the drawing-tiles (earth, grass, sea, etc. in short, all the details drawn) DXT1 format
the MASK tiles are there to define the water shine/reflection effects, and the night lights. DXT5 Format
the ELV tiles define the relief. (ELV_Mod tiles modify the relief defined in ELV). Format... uh...

It is in the latter case that tiledit is useful. But it's very complicated and this software is rather rough...
Note that Face has made very useful tools, but for to start I think it's better to begin by making the "SURF" tiles.
MASK tiles are easy to make from SURF tiles.

Maybe this could help you : I made a little tutorial (but in French, sorry) here :
http://orbiter.dansteph.com/forum/index.php?topic=14669.0

It took me a while to be able to make tiles, but now that I know how to do it, it's quite easy...

I am doing a whole region: French Guiana here :

So, it is just a quick summary of the problem with tiles in Orbiter 2016.
Of course I can help you if you want.
Except for the "ELV" tiles: it's quite complicated and it doesn't really amuse me... ?

#### llarian

##### Well-known member
If you must have an English translation, my version of Chrome, if you right click on the page, the menu that comes up has an entry "translate to English". Worked fine for me. If you are desperate enough, let me know, I saved English copies of the pages.

Replies
0
Views
146
Replies
46
Views
2K
Replies
5
Views
453
Replies
15
Views
239
Replies
18
Views
1K

format: plain


text:
# Discrete Math Research Group at the University of Regina

We are the discrete math research group in the Department of Mathematics and Statistics at the University of Regina. Our group meets weekly throughout the year to work on open problems in discrete math. This is not a seminar series but rather a working group. We are always looking for new and interesting problems so contact us if you have a problem to suggest!

## Current Members

 Shaun Fallat Professor Karen Meagher Assistant Professor Boting Yang Professor Ferdinand Ihringer Post Doctoral Fellow Mohammad Adm Post Doctoral Fellow Alison Purdy Post Doctoral Fellow Ryan Bergen Masters Student Adam Gore Masters Student Sam Jaques Undergraduate Student

## Past Members

 Guanglong Yu Visiting Researcher Ryan Tifenbach Post Doctoral Fellow Bahman Ahmadi Fatemeh Alinaghipour Robert Bailey Yi-Zheng Fan Chris Fisher Pavel Semukhin Michael Cavers Shahla Nasserasr

## Update on Oviods

We have submitted our paper Oviods in Generalized Quadrangles to Journal of Combinatorial Designs. The paper is available at arXiv.

## Update on Infection in Hypergraphs

We have submitted our paper Infection in Hypergraphs to Journal of Graph Theory. The paper is available at arXiv.

## Related Papers

Our groups has produced several papers (links are below) but there has been recent work that continues projects started in this groups. Some links are here; if you know of other papers that are the result of work started in the DMRG, please let me know.

Wayne Barrett, Shaun Fallat, H.Tracy Hall, Leslie Hogben, Jephian C.-H. Lin, Bryan L. Shader, Generalizations of the Strong Arnold Property and the minimum number of distinct eigenvalues of a graph

Robert F. Bailey, Andrea C. Burgess, Generalized packing designs.

## Winter 2016

This term our meeting times are Thursday 10-noon in AH 412. We are continuing to work on "Infection in Hypergraphs". I have emailed out the working notes to everyone. We ought to think about 2-designs and hypertrees.

## Hypergraphs

We have started a new project, generalizing zero forcing to hypergraphs. I will post notes soon. We defined what I am called "hyperpaths" today and we are conjecturing that the infection number of a hyperpath is bounded by the zero forcing number of its host tree.

## Announcement

So it is good news or bad news? This summer (2013) Bahman Ahmadi and Fatemeh Alinaghipour have both completed their Ph.D.s here at the Univeristy of Regina. A big congratulations to you both! But this means they will be leaving and will be missed. Good luck and I hope that we can continue to work together! Further, Shahla Nasserasr has moved to Fort Lauderdale where she is an assistant professor at Nove Southeastern University. I delighted for you, jealous and sad to see you go!

## Announcement

Yay! Our paper Minimum number of distinct eigenvalues of graphs has appeared in the Electronic Journal of Linear Algebra. We still have many open questions related to this problem and we are hoping to return to it in January of 2014.

## New Project Update

We have made some progress on our project on covering arrays, here are our notes . I don't think that this project will go much further as there are currently better ways to construct covering arrays and many of the other ideas we tested did not work.

## New Project Jan. 2013 - Group Constructions of Covering Arrays

For the new term we are starting a new project. This project has to do with the construction of covering arrays using groups. We are now meeting on Tuesdays from 2-4pm in ED310. Here are the notes from Tuesday's meeting. I also have paper that I wrote on this topic you can get it here and there was another paper on this topic too.

Also we are finishing up our paper on the minimum number of distinct eigenvalues for a graph. We will add a link here when it is done.

## Announcement

Our paper on Minimum Universal Rank has appeared! Here is the link to it: MUR paper in LAA

## Summer 2012 Project: Minimum Number of Distinct Eigenvalues

Here are the notes from July 19.

For a graph $G$ on $n$ vertices, $S(G)$ denotes the set of all real $n \times n$ symmetric matrices with $A=[a_{ij}]$ such that $a_{ij}\neq 0$, for $i\neq j$ if and only if vertices $i$ and $j$ are connected by an edge. The minimum number of distinct eigenvalues of $A$ when minimum is taken over all matrices in $S(G)$ is denoted by $q(G)$. We have many questions about this parameter $q$. For example $q(G) =1$ if and only if $G$ is the empty graph. So for which graphs $G$ is $q(G) =2$? So far we have found far many more than we ever expected! On the other end of the scale, $q(G)$ is equal to the number of vertices in $G$ if and only if $G$ is a path. So for which graphs $G$ is $q(G)$ one less than the number of vertices?

Here are notes from our meetings so far (thanks Fatemeh!).

We also have some results for cycles and complete bipartite graphs.

## New project! Fall 2011

We have selected a new project, it is the minimum number of eigenvalues for a graph. We are ready for a new topic. Below is information on the three proposed topics, go to topic poll to select the topics that are intersting to you. (Vote for all if you wish, but only vote for topcis that you would be willing to work on)

### Strength-3 Sperner Set Systems

Here are my notes on strength-3 Sperner set systems , they are just my working notes so there are errors and typos!

### Minimum number of distinct eigenvalues of a graph

These are Shahla's notes on this problem .

### (3,1,1)-Generalized Packing Designs

The (first draft of) the paper on generalized packings is here. The case of (k-2,1,1) is outlined in section 3.5; while the case of (2,1,1) is discussed in detail in section 5.3. Two papers on Kirkman squares are here and here. A paper on SOMAs is here.

## The Minimum Universal Rank of a Graph -- Summer 2011

Here is the reference for our paper:
B. Ahmadi, F. Alinaghipour, S. Fallat, Y. Fan, K. Meagher and S. Nasserasr. The minimum rank of universal adjacency matrices.
Submitted to Linear Algebra and its Applications. Oct. 2011
Available at (arXiv).

### Oct 31

We are just about ready to submit our paper on the mur of graphs. The paper will be posted here soon.

### Aug 18

Here are the notes from Aug 18 .

We have started writing up a paper on our results. Shahla is the editor on this!

### July 28

Here are the
notes from July 28 .

The notes are short, (I know I was tired on Thursday!). I do now have a proof of the theorem with the condition that r is not equal to s+1. I will try to find the mur of this graph when r = s+1.

### July 7

Here are the
notes from July 7 (thanks again Shahla!)

Today we were getting results like crazy - here are some highlights:
1. mur of a cycle on n vertices is n-3
2. mur of a path on n vertices is n-2. We have a proof of this but not a construction of a universal matrix that meets this bound.
3. If G has n vertices then mur(G) is no larger than n-2.
Open questions
1. What is the mur of a tree?
2. how does the mur of a graph change when an isolated vertex is added. The mur can stay the same, go up by one or two. If the graph is regular, then the mur can only go up by at most one.
3. How does adding a pendent edge to a graph change the mur?

### June 30

Here are the
notes from June 30 (thanks Shahla!)

Questions of note are:
1. Is min universal rank monotone on induced subgraphs? The answer seems to be an easy yes but Shaun Pointed out that the degree sequences may change on an induced graph. So this question appears to be a little tricky. It would be interesting to find a graph that has an induced subgraph whose min universal rank is larger than the original graph. We may need more examples of graphs with large min universal rank before we can find such a graph.
2. Can we find a direct proof that the only graphs with min universal rank equal to 1 are the union of two complete graphs or the union of a complete graph with any number of isolated vertices (or their complements)
3. Can we say anything interesting about regular graphs that have the degree as the eigenvalue with the strictly largest multiplicity?
4. For graphs G and G can we say anything about mur (G \cup G) or (G \cup H)?

### June 23

This project is very closely related to our last project. If G is a graph then any matrix that is a linear combination of (i) the adjacency matrix of G, (ii) the all ones matrix (iii) the identity matrix (iv) the diagonal matrix with the degrees of the vertices on the diagonal is called a Universal Adjacency Matrix (UAM) of G. Our goal is to find the minimum rank over all UAMs of G.

Here are the notes (thanks Shahla)) from out last meeting. Since our meeting, I have found a graph with min universal rank equal to 1. Further, Shaun has a formula for the minimum universal rank of a connected regular graph. Our next meeting will focus on disconnected graphs.

## Past Project: The Minimum Rank of a Graph -- Fall 2010

Both Fatemeh and Shaun have made comprehensive notes on this project from last term in case anyone needs a review! Here they are: Shaun's notes, Fatemeh's first set of notes and Fatemeh's secend set of notes

Here is an update on the Open Problems .

Here the some Open Problems that we have compiled. We will start working on the most appealing of these Friday November 19th.

During the Fall 2010 semester, Shaun Fallat will lead this group through the topic of the minimum rank of a graph. In general the setting is as follows: The minimum rank problem for a simple graph is to determine the minimum rank among, for example, all real symmetric matrices whose zero-nonzero pattern of off-diagonal entries is described by a given simple graph G. We note that the maximum rank is always the order of G, and it is straightforward that any rank between the minimum and full rank may be achieved. It turns out, that the zero-nonzero pattern described by a graph has significant influence on the minimum rank.
Example: A matrix associated with a path on n vertices is a symmetric tridiagonal matrix (up to labeling) with nonzero sub- and super-diagonal and thus has minimum rank n-1, whereas the complete graph on n vertices has minimum rank 1. The plan is to provide an introduction to this topic, including an overview of the notation and a survey of a number of important related results. The goal after a few introductory lectures would be for the group to work on some relevant open problems that are of current interest (these will be discussed within the group).

### A sample of applications in this area:

- spectra of graphs and combinatorial inverse eigenvalue problems
- singular graphs, nullity of the adjacency matrix;
- biclique decompositions and the biclique partition number (Graham-Pollack Theorem);
- Hermitian rank and inertia;
- Lovasz theta function and orthonormal labellings of graphs.
- computation complexity

### A short list of relevant references are listed below along with linked pdf files:

#### Minimum Rank of Graphs

1. AIM minimum rank-special graphs work group, 2008 Zero forcing sets and the minimum rank of graphs
2. Barioli and Fallat, 2004 On two conjectures regarding an inverse eigenvalue problem for acyclic symmetric matrices
3. Barioli and Fallat, 2007 On the Minimum Rank of the Join of Graphs and Decomposable Graphs
4. Barioli, Fallat, and Hogben, 2004 Computation of minimal rank and path cover number for certain graphs
5. Barioli, Fallat, and Hogben, 2005 On the difference between the maximum multiplicity and path cover number for tree-like graphs
6. Barioli, Fallat, and Hogben, 2005 A variant on the graph parameters of Colin de Verdiere: implications to the minimum rank of graphs
7. Barrett, van der Holst, and Loewy, 2004 Graphs whose minimal rank is two
8. Berman,  Friedland, Hogben, Rothblum, and Shader, 2008  An upper bound for the minimum rank of a graph
9. Fallat and Hogben, 2007 The minimum rank of symmetric matrices described by a graph: a survey
10. van der Holst, 2008 Three-connected graphs whose maximum corank is at most three
11. van der Holst, Lovasz, and Schrijver, 1999 The Colin de Verdiere graph parameter
12. Johnson and Leal Duarte, 1999 The maximum multiplicity of an eigenvalue in a matrix whose graph is a tree

#### Minimum Semidefinite Rank of Graphs

1. van der Holst, 2003 Graphs whose positive semi-definite matrices have nullity at most two
2. Jiang, Mitchell, Narayan, 2008  matrix digraphs and minimum semidefinite rank
3. Lovasz, Saks, Schrijver, 1989 Orthogonal Representations and Connectivity of Graphs, 2000 Correction
4. Narayan et al, 2008  On minimum rank of positive semi-definite matrices with a given graph

## Past Projects

### Sample Compression

We currently studying a problem that is motivated by a problem in theoretical computer science. The problem has to do with sample compression and VC-Dimension. Here is an introduction to the problem.

### Generalized Covering Designs

Here is the reference to our paper on this topic. Generalized covering designs and clique coverings (with Andrea Burgess, Michael Cavers and Karen Meagher), Journal of Combinatorial Designs 19 (2011), 378–406; doi: 10.1002/jcd.20288 (arXiv).

### Covering Arrays

The question we asked is the following: Is it possible to get good bounds on small covering arrays using eigenvalues of non-uniform partition graphs?

We were able to find several eigenvalues for these graph and using these se were able to find some bounds on the sizes of small covering array. Unfortunately, the bounds we found are not the best known bounds. A summary of this work is available here. This project will likely be continued at some point. One approach would be to develop a better method to find eigenvalues with the goal of finding smaller eigenvalues that will give better bounds. We did return to the study of covering arrays. Our goal was to prove that for small covering arrays (specifically, arrays with alphabet size k and between k^2 and k^2+k columns) that the optimal arrays can be achieved using balanced covering arrays. We have an approach which involves finding a clique partition for a certain multipartite graph, namely the graph K_{k,2,2,...,2}. Unfortunately we were unable to find appropriate bounds on the size of a clique partition for this graph. If you have an ideas let use know!


text:
# How to optimize collision detection in a lane-defense game?

Somebody told me that don't use the physical collision detection(don't use Collider,Rigidbody,Raycasting) because performance loss.instead of it use the mathematical way for collision detection.

Physical collision detection:

Raycasting is a very useful and powerful tool available on the physics engine. It allows us to fire a ray on a certain direction with a certain length and it will let us know if it hit something. This however, is an expensive operation; its performance is highly influenced by the ray’s length and type of colliders on the scene.

in this game enemies randomly create in some points.is it that better instead of checking by Raycasting call the fire(); method(foreach plant in them row) when created zombies?

mathematical collision detection:

Vector3.Distance(a,b) is the same as (a-b).magnitude.

float dist = Vector3.Distance(other.position, transform.position);

is better checking distance than using mentioned components(Collider,Rigidbody). he believes using Colliders and Rigidbody component produce lag in game.

First of all, "performance loss" is only an argument in situations where performance actually matters. When your framerate is good enough and your code is easier to read and maintain with colliders and raycasting, then by all means, stop fixing what isn't broken.

But in the case of a lane defense game like plants vs. zombies, you have very simplified game physics where the Unity collision detection engine indeed seems overkill.

1. Objects can only collide with objects in the same lane
2. When two objects are in the same lane, all that matters is the x-coordinate and the width of the objects involved.
3. All objects only move in one direction and only collide head-on. So you only need to check for collisions in one direction.

First you need to know which lane each object is in. There are several ways you could do that.

• You could make each lane an own object in your scene hierarchy and all objects on that lane child-objects.
• You could have a public int lane variable on each object which says which lane it is on.
• You could have a List<GameObject> for each lane somewhere.

Each of these approaches has advantages and disadvantages. Pick the one which seems to fit best into your overall architecture.

If you want to check collisions of an object obj with other objects, get all objects in the same lane. Then if you want to check for a collision to the right, do if (other.x - obj.x) < (obj.width + other.width) / 2 for each eligible object in that lane. To check for a collision to the left, do if (obj.x - other.x) < (obj.width + other.width) / 2.

A side-note about the Rigidbody component: You only need rigidbodies when you want to have kinetic physics (gravity, mass, friction, objects bouncing off each other, etc.). When your game isn't supposed to have anything like that, you shouldn't put a rigidbody on anything. I am not saying that adding realistic physics couldn't be an interesting spin on the overused tower defense formula, but when you want to create an authentic Plants vs. Zombies clone, you likely don't want that. When all you want is collision detection, then all you need is a Collider.

• I was going to say the same so +1. Unless you are having performance problems, and this is a significant part of the work done, optimizing this isn't going to really get you anything. Good enough is good enough, by definition! – Alan Wolfe Dec 5 '16 at 16:13
• Re: the side-note, I know in earlier versions of Unity moving a collider without a rigidbody was very slow. I understand they've made this much much faster in recent versions than it used to be, but I haven't verified whether it's faster or slower than moving a kinematic rigidbody. This sounds like it could be a case worth profiling each way to see if it makes a difference.(If you're using the physics system at all, that is) – DMGregory Dec 5 '16 at 23:47

It all depends on your game. Typically you would use distance methods combined with other methods like GJK and SAT to calculate the collision detection mathematically. Using raycasting (in combination with the methods above) is good for things that move very fast. If you have two objects moving towards each other at a high enough speed such that they pass each other during the one frame, then you would need to raycast to make sure that you dont travel through the object.

e.g.:

frame 1   |   frame 2
[A]><[B]  |  <[B]  [A]>

(because you are just adding velocities to their positions, you are not moving them one pixel/unit at a time)

However, if you are making a game like Plants V Zombies as you pictured, you could get away with far less.
You know that objects are only on one axis and things fit into cells. You can simply check whether or not x values overlap/pass each other.
Or, more simply, check what cell an object is in and see if something else was there already