Keywords: biocompatibility, phosphorylcholine, phosphatidylcholine, biomaterials, PMHS, anti-fouling

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Thin phosphatidylcholine films as background surfaces with further possibilities of functionalization for biomedical applications

Lara Tauk, Thierry Thami, Lynda Ferez, Armagan Kocer, Jean-Marc Janot,

Philippe Dejardin

To cite this version: Lara Tauk 1 , Thierry Thami 1 , Lynda Ferez 1 , A. Kocer 2,3 , Jean-Marc Janot 1 , Philippe Déjardin 1 * A c c e p t e d M a n u s c r i p t

Introduction

The efficient functioning of sensors for biomedical analysis is dependent on the integrity and accessibility of the surface-fixed molecule designed for molecular recognition, on the one hand, and on the surroundings designed for neutral behavior, especially to avoid nonspecific adsorption, on the other hand. Thus blocking buffers are proposed in diagnostic kits with for instance albumin [1,2]. In addition, fabrication of polymer films on solid supports with defined structures and properties such as uniformity, stability, and reproducibility is crucial in the development of thin-film chemical sensors. It is still difficult to fabricate ultrathin polymer films that are uniform, continuously defect free, and stable.

Moreover, controlled growth of stable polymer films at the nanoscale level, which is important in many applications, remains a challenge. Some control of film thickness, uniformity, stability is needed to achieve reproducibility [3].

A crucial aspect in the design of biomaterials surfaces is to achieve control also over the interfacial interactions between the synthetic material/device and the biological medium [4,5]. Protein-resistant ("non-fouling") surfaces are particularly important in the context of blood-contacting biomedical devices, and as non-interactive background for bio-diagnostic surfaces. There is a very limited number of effective non-fouling surfaces available to meet the challenges of practical applications [6]. Poly(ethylene glycol) (PEG) and oligo(ethylene glycol) (OEG) have been widely used to resist nonspecific protein adsorption [7,8] owing to their ability to form a hydration layer via hydrogen bonds but the strength of these bonds decreases as the temperature increases [9]. Moreover, PEG or OEG can decompose in the presence of oxygen and transition metal ions [10]. Recently zwitterionic (sulfobetaine; carboxybetaine) materials have been found to exhibit ultralow protein adsorption [11,12] A c c e p t e d M a n u s c r i p t 4 (fibrinogen adsorption < 5 ng cm -2 ). This is due to the zwitterion structure which retains a large amount of tenaciously held water independent of temperature because of hydration via ionic solvation [13]. The interface is expected to be electrically neutral over a wide pH range

(5-9) with phosphate and sulfonate zwitterions while variations can be exploited with carboxy groups. Coated surfaces with zwitterionic phospholipids have been shown to confer high resistance to protein adsorption [14]. The mechanism of protein adsorption resistivity on the phosphorylcholine modified surface is thought to be based on the interaction between water and phosphorylcholine groups. It is reported that when the water fraction on the polymer surface is maintained at a higher level, the proteins can contact the surface reversibly without significant conformational changes [15]. The large amount of water around the phosphorylcholine groups is thought to repel proteins and even prevent conformational changes of the few adsorbed proteins [16][17][18].

Recently a zwitterionic trimethoxysilane was synthesized for direct grafting on oxidized silicon wafers [19]. In the present work we applied the strategy of surface anchoring a reactive poly(methylhydrosiloxane) (PMHS) network, as in the development of a sensor for nitroaromatics [20], followed by covalent grafting of phospholipids bearing the zwitterionic phosphorylcholine head on the polymer active sites (SiH) via the hydrosilylation reaction (Fig. 1a). X-ray photoelectron analysis was used to follow the reaction. The captive air bubble contact angle in water was measured to characterize the samples surface hydrophilicity.

We considered especially thin PMHS films (10-200 nm), extending the previous study on films of thickness in the micrometer range [21], with the aim of creating low roughness surfaces not exhibiting the grooves shown in that previous work but conserving their proteinrepellent character. Protein adsorption was analyzed by the normal scanning confocal fluorescence technique.

A c c e p t e d M a n u s c r i p t 5

Materials and Methods

Chemicals

Both the precursors methyldiethoxysilane HSi(CH

Proteins and labeling

Bovine serum albumin (A-7638), cytochrome C (C-2506), -chymotrypsin (C-4129), avidin (A9275) were purchased from Sigma-Aldrich; some avidin from Fluka (No. 11368).

Given their isoelectric point, at physiological pH 7.4, BSA (67 000 g mol -1 , pI 5.6) is negative, -chymotrypsin (25 300 g mol -1 , pI 8.1) slightly positive, avidin (66 000g mol -1 , pI 10) and cytochrome C (12 400 g mol -1 , pI 10.2) strongly positive.

A c c e p t e d M a n u s c r i p t 6 Labeling of proteins was performed with Alexa-fluor-594 succinimidyl ester (InvitroGen, A30008). Typically 500 µL of protein solution were added to dry fluorophore Alexa-594 in molar ratio 1:1 and allowed to react for 0.5 h at 20°C. Avidin was also labelled via previous biotin-ethylenediamine hydrobromide (Sigma B9181) reaction with alexa succinimidyl ester as described elsewhere [22]. The mixture was then put in an ad hoc microtube with filter (Biospin P6) and centrifuged at 16 000 g for 1 min according to the supplier of the kit (Labelling kit A10239, InvitroGen). The labeling ratio [Alexa] / [protein] (0.3-0.5) was determined from the UV absorbances at 280 nm where both the label ( 280 -Alexa = 50 400 M -1 cm -1 ) and protein absorb and at 590 nm where only the label ( 590 = 90 000 M -1 cm -1 ) [23] absorbs. Protein solutions were prepared in 10mM sodium phosphate buffer pH 7.4 with 0.15M NaCl in de-ionized water (MilliQ system, Millipore) and stored at 4°C.

Liposome preparation and labeling

One hundred milligrams of L--Phosphatidylcholine (Soy-20%) (Avanti Polar Lipids Inc. 541601 -dioctadecyl-3,3,3',3'-tetramethylindodicarbocyanine perchlorate solution (Invitrogen Inc.) (1mg/ml in methanol). After chloroform had been thoroughly removed under vacuum, phosphate buffered saline (PBS, 10mM, pH 8.1, 150mM NaCl) was added and mixed in. Aggregated particles were then sonicated until complete dissolution. The mixture was then taken through a freezethaw procedure five times. This procedure involved freezing the solution by immersion in liquid nitrogen, followed by thawing by immersion in 60 °C water. After the freeze-thaw process, immersion in liquid nitrogen and stored at -80°C. Before use, the vesicle suspension was heated by immersion in 60°C water and regularized by extrusion through polycarbonate ). We subjected the samples to 11 passes through the membrane.

The same procedure without the label DiD was applied to obtain unlabeled liposomes whose size distribution was measured by photon cross-correlation spectroscopy (Nanophox, Sympatec -France).

Methods of preparation of the support 2.4.1 Substrate cleaning and activation

Silicon wafers Si(100) (ACM, France) square strips of 2 × 2 cm 2 were used as substrates for spin-coating deposition. To bond covalently the PMHS thin films to native oxide silica (thickness ca 2 nm) and to glass surfaces, they were cleaned and activated with oxygen plasma for 60 seconds.

PMHS film

PMHS thin films were prepared at 22 ± 1°C by sol-gel polymerisation of DH and TH as crosslinker, as described elsewhere [24]. This procedure gave layers of reproducible homogeneity and thickness as controlled by ellipsometry (Plasmos SD 2300 ellipsometer (München Germany)) [25]. We used refractive index n =1.4 for PMHS.

Grafting PMHS with phospholipids

a-by casting: the phospholipid solution was prepared under argon. 20 mg of PL were dissolved in 8 mL of dry toluene (2.5 mg / mL), with additional 7 µL of the Karstedt catalyst For both methods, the samples were then rinsed successively in different toluene/chloroform mixtures from 100/0 to 0/100 (% vol.) with a gap of 20% and dried under a stream of Argon. We will refer to the PMHS layer having reacted with PL as PL-PMHS(h nm) where h is the PMHS initial thickness measured by ellipsometry.

Techniques of characterization of the support 2.5.1 X-ray photoelectron spectroscopy

The surface elemental compositions of unmodified and modified PMHS surfaces were analysed by X-ray photoelectron spectroscopy (XPS). The spectrophotometer (ESCALAB 250, Thermo Electron, UK) was equipped with a monochromatic Al K (1486.6 eV) radiation source. The acceleration tension and power of X-ray source were 15 kV and 100 W, respectively. The samples were analysed at a pressure in the 10 -9 mbar range. The electron take-off angle with respect to the sample surface was 90°. The analysed spot size was approximately 400 m 2 . The XPS composition corresponds to depths of 5-10 nm. Survey scans (0-1350 eV) at low resolution were performed to identify constitutive elements. High resolution C 1s , Si 2p , O 1s , N 1s and P 2p spectra were recorded to obtain more detailed information provided the various surface atomic ratios from the corresponding peak areas, by assuming the total area corresponded to 100%, after correction with the theoretical sensitivity factors [26]. The spectra of both pristine PMHS and PL-PMHS were calibrated using the hydrocarbon contaminant or alkane C 1s peak set at 284.8 eV. In both cases, the peak of Si-CH 3 was found at a binding energy (BE) of 284.0 eV in agreement with PDMS polymer at 284.4 eV [START_REF] Beamson | High resolution XPS of organic polymers[END_REF].

Captive air bubble contact angle in water

The samples were characterized by captive air-bubble (7.6 µL) contact angle (GBX -Digidrop, Romans, France). The contact angle was calculated after 1 min using computerized image analysis. The data are relative to the angle through the liquid as generally defined [START_REF] Hong | [END_REF],

in opposition to its complement angle to 180° through air as used in a previous work [21]

AFM

Atomic Force Microscopy (AFM) experiments were performed using a Dimension 3100 microscope equipped with a Nanoscope IIIa controller system (Digital Instruments, Veeco Metrology Group). AFM images were obtained by scanning in tapping mode in water or under ambient conditions in air using silicon SPM probes (stiffness k 2 N/m, resonance frequency of 67 kHz, pointeprobeplus, Nanosensors). The root mean square average roughness (R q ) was analyzed with the Nanoscope software (version 5.31r1).

Adsorption: Flow cell and Determination of interfacial concentration

Results and Discussion

Physico-chemical characterization of PMHS and PL-PMHS films

The Q water gave rise to an additional increase of thickness. Over the range examined we can attribute a mean 26% increase of thickness from the reaction with phospholipids and an 8 nm increase from conditioning the material in water. Conditioning the PL-PMHS for several days in water led to rolling bubble (0°) possibly stabilized at a slightly higher contact angle (Fig. 1d). The structures of the PMHS and PL-PMHS films were examined by AFM (Fig. 2).

PMHS roughness was lower than 1 nm for a very thin layer (12-20 nm) while structures appeared for 125nm. Reaction of PL induced always an increase in roughness (Table 1). The 12 nm thin PMHS sample showed a roughness R q of 0.4 nm with a few defects. PL grafting induced an increase of roughness to 2.03 nm as measured in air. Immersion in water decreased the roughness to 1.28 nm. This may be partly due to the reorganisation of phospholipids chains in the presence of an aqueous medium in order to minimise the free energy of the system. The minimum 0.9 nm for the PL-PMHS roughness was found for ca. 20 nm thick PMHS.

A c c e p t e d M a n u s c r i p t Table 1 Roughness R q over 10µm × 10µm samples of PMHS and derived PL-PMHS for different initial PMHS thickness h.

Chemical characterization: XPS analysis of the interface

The surface elemental compositions of pristine PMHS and PL-PMHS were determined from high resolution XPS spectra. To summarize the characterization of PL-PMHS layers, A c c e p t e d M a n u s c r i p t

The adsorption of avidin was examined on different PL-PMHS substrates derived from the PMHS initial thicknesses of 7 nm and 180 nm (Fig. 3b). The interfacial concentration was 1.2 and 0.1 ng cm -2 respectively, with dispersion around 1 ng cm -2 . Let us recall that there was a slight displacement in the plane of substrate between the normal scannings to avoid repetitive exposure to the laser beam which could induce a photobleaching effect. This procedure constituted then also an examination of the interface homogeneity.

Conversely, adsorption on sulfochromic acid treated glass was large with an initial linear variation up to ca. 0.1 µg cm -2 . The initial kinetic constant k was 7.4 × 10 -5 cm s -1 . With D 6 10 -7 cm 2 s -1 , the transport limited constant k Lev is 2.65 10 -4 cm s -1 . Applying the expression [31,32]

k a = k (b 1 u + 1) (b 2 u + 1)/((u-1) (a 1 u-1))
, where u = k/k Lev and numerical coefficients a 1 = 0.556, b 1 = -0.681, b 2 = -0.0484, led to k a 1.0 × 10 -4 cm s -1 . In any case, the phospholipid treatment was very efficient in preventing avidin adsorption, even at very small thickness of PMHS (7 nm), exhibiting the good quality of the coverage and the corresponding screening of the substrate.

The adsorption of Alexa-BSA was studied on PMHS(20 nm), PL-PMHS(20 nm) and PL-PMHS followed by HMDS capping, denoted H-PL-PMHS(20 nm) (Fig. 3c). All surfaces were immersed overnight in water and exposed to flowing buffer and solution with sulfochromic acid treated glass as the other face. Whatever the surface, when adsorption occurred no rapid desorption was observed by flowing buffer. The PMHS surface exhibited some adsorption, 10 ng/cm 2 over 20 min without a plateau (k = 1.0 10 -6 cm s -1 ). The H-PL-PMHS showed a very small interfacial concentration ( = 0.8 ± 0.5 ng/cm 2 ) comparable to 0.5 ± 0.3 ng/cm 2 observed on PL-PMHS. It might reflect the burying of the trimethyl groups in the hydrophobic domains of lipid chains avoiding their direct exposure to the aqueous medium thus preventing hydrophobic interactions with the protein.

A c c e p t e d M a n u s c r i p t

Our studies showed that phosphorylcholine modified PMHS layers experienced almost "zero" protein adsorption. The decrease due to phosphorylcholine groups agrees also with previous studies to improve the biocompatibility of poly(dimethylsiloxane) (PDMS) [33]. The polymer of 2-methacryloyloxyethyl phosphorylcholine (MPC) was grafted by surfaceinitiated photo-induced radical polymerization. The in vitro single protein adsorption on the poly(MPC)-grafted PDMS decreased 50-75% compared to the unmodified PDMS. On poly(ether-ether-ketone) (PEEK) treated with MPC, BSA adsorption studies [34] showed a significant effect of MPC till 90% adsorption reduction with respect to PEEK.

Adsorption of labeled (DiD) liposomes of L--Phosphatidylcholine (diameter 400 nm)

was measured by scanning confocal fluorescence as for the proteins. Based on an average area per head of 0.5 nm 2 or diameter per head of 0.8 nm, the adsorption at different interfaces is shown in Fig. 4. It can be seen that PL-PMHS constitutes a repellent surface with respect to L--Phosphatidylcholine liposomes, despite this lipid being not just a pure simple lipid but a mixture of lipids (24% PC, 18% Phosphatidylethanolamine, 11.5% Phosphatidylinositol, 4.3 % Phosphatidic acidA, 4.6% LysoPC and some other unknown lipids).

Functionalization of PL-PMHS Surface

The XPS analysis after PMHS hydrosilylation with PL exhibited the side reaction with water giving silanol groups, which may evolve to siloxane bridges too. Such interfacial silanols could be available for subsequent reaction. functional groups in the absence of water and catalyst. Moreover, this demonstrates that the Karstedt'catatyzed side reaction of SiH with water plays a major role in the formation of interfacial silanol on such PL-PMHS surface. After coupling the alexa probe, the silanol concentration can be thus estimated by assuming that the coupling reaction is total. According to the method developed above for determination of interfacial concentration, the mean degree of functionalization of the PL-PMHS layer was measured to be 3.0× 10 -2 nm -2 .

Assuming that all molecules were grafted at the interface the mean distance between the sites was 5.7 nm. This order of magnitude is acceptable for a quite dense packing of proteins on a neutral background and can be probably modified by changing the experimental conditions. In addition, we showed that the silanols of the interface could react also with aminomonoethoxysilane to provide a phosphorylcholine background surface with amino A c c e p t e d M a n u s c r i p t 21 groups available for amide junctions (Scheme 1). This was carried out with the alexa ester leading to the same interface as before with the same site density.

Conclusion

Polymethylhydrosiloxane anchored on an activated oxidized silicon wafer or glass can be deposited as a very thin film of low roughness and functionalized with phospholipids bearing a phosphorylcholine head. The functionality of the surface was analyzed by XPS and the correlated wettability change determined by contact angle measurements with captive air bubble. The new interface was observed to be very hydrophilic and protein-repellent at neutral pH in phosphate saline buffer. L--Phosphatidylcholine liposomes containing different phospholipids could not bind to such interfaces. Thus tailored surfaces can be produced to fix specific cells with appropriate functionalization. As the stiffness is a pertinent parameter in cell spreading [35], one perspective would be to vary the DH/TH ratio in the synthesis of the PMHS films with better control of water in subsequent grafting. We have shown that the silanol groups originating from the side-reaction with traces of water provided possibilities for further functionalization. The prevention of protein adsorption is attributed to the zwitterionic character of the phosphorylcholine head which maintains a water-rich layer at the interface.

We found that a 20 nm thick PMHS layer led to very flat surfaces with roughness less than 1 nm. We have shown finally that the protein-repellent interface can be easily provided with amine functional groups. Therefore such protein-repellent interfaces can be useful in the biomedical domain, e.g. for biosensors, biomaterials and cell culture, by reducing strongly the non-specific adsorption, on the one hand, and offering in addition possibilities for grafting desired functions, on the other hand. Moreover, the covalent coverage with phospholipids and the sites for further functionalization are generated in a one step process.

A c c e p t e d M a n u s c r i p t 1 Thin

 1 Tauk, Thierry Thami, Lynda Ferez, Armagan Kocer, Jean-Marc Janot, et al.. Thin phosphatidylcholine films as background surfaces with further possibilities of functionalization for biomedical applications. Colloids and Surfaces B: Biointerfaces, 2013, 101, pp.189 -195. 10.1016/j.colsurfb.2012.06.028. hal-01688768 phosphatidylcholine films as background surfaces with further possibilities of functionalization for biomedical applications.

A c c e p t e d M a n u s c r i p t 7 membrane

 7 filters (Avestin Inc.) of pore diameter 400 nm mounted in a mini-extruder (Avestin Inc.

A c c e p t e d M a n u s c r i p t 8 (

 8 xylene solution of platinum divinyltetramethyldisiloxane complex). The molar ratio of phospholipid over hydrogenosilane group SiH was 1.5. PMHS coated silicon wafers (2 × 2 cm 2 ) and glass surfaces (1.5 cm 2 ) were covered by 200 µL and 80 µL of phospholipid solution respectively. The samples were kept for one hour under a cap to slowly evaporate the solvent and then left in open air for quick evaporation. b-by immersion: silicon wafers were immersed in the phospholid solution (2.5 mg/mL) for one hour.

  A c c e p t e d M a n u s c r i p t 9 about the nature of the surface. The peaks were fitted with Gauss-Lorentz curves. They

A c c e p t e d M a n u s c r i p t 10 The

 10 experiments were performed at T = 19°C in a slit flow cell of thickness 100 µm and flow rate corresponding to wall shear rate 1000 s -1 . Confocal measurements[29,30] with inverted microscope configuration were performed at 3 cm from the slit entrance. Interfacial concentration was evaluated as follows: the fluorescence signal F sol from solution at concentration C is relative to an effective volume V while the signal F surf from surface concerns interfacial concentration over area A. F surf A andF sol C V therefore = (V/A) (F surf / F sol ) C.In a previous paper[29] the order of magnitude of V/A was estimated from the focus radius for A and 1 µm 3 taken as the confocal volume V. A more precise determination is obtained considering the adsorbed layer as a Dirac function of fluorescence[21]. Then V/A = w D is the area under the normalized fluorescence peak f i (y) = F i (y) / F i (0) resulting from the convolution of the fluorescent interface positioned at y = 0 with the laser beam.

  ellipsometric thickness of PMHS film on oxidized wafers as a function of initial concentration of monomers (DH and TH) is provided in Fig. 1b. The variation was linear with a slope of 95 ± 4 nm M -1 . After hydrosilylation reaction had proceeded over one hour by means of casting or immersion the thickness of the PL-PMHS layer was measured and the hydrophilicity characterized by captive air bubble contact angle (Fig. 1c). Both techniques gave the same results suggesting the occurrence of a quick interfacial reaction over less than one hour and efficient removal of excess phospholipids in the casting method. An average A c c e p t e d M a n u s c r i p t 11 angle of 40° was observed whatever the initial PMHS thickness, much below the value of 90° observed with hydrophobic PMHS. The ellipsometric thickness increased as expected after reaction of the PMHS layer with phospholipids. Conditioning the samples overnight in Milli-

Figure 1

 1 Figure 1 Method of surface treatment and physico-chemical characteristics of the films. (a)

Figure 2

 2 Figure 2 Characterization of the films by atomic force microscopy. AFM pictures (5 µm × 5 µm) of PMHS layers (thickness h) and of their derived PL-PMHS layers. Corresponding

A c c e p t e d M a n u s c r i p t 15 3. 3

 153 they are very hydrophilic due to the fast reaction of PL at the top of the layer. There was however competition with the side reaction of SiH with traces of water giving SiOH groups which may recombine to produce siloxane bridges. The formation of new SiOH or SiOSi bonds in the PL-PMHS layer was shown by the evolution of the two distinct doublets (Si 2p 3/2) of the Si 2p PMHS spectrum by reaction with PL at binding energies 101.2 (21% 102.3 eV (79% We will see below how the density of available SiOH can be determined and used for functionalization. Protein adsorptionThe wettability behaviour of the PL-PMHS surfaces (Fig.1c-d) was indicative of a probable protein-repellent character. We investigated protein adsorption from single protein solution in PBS buffer pH 7.4 (avidin, bovine serum albumin (BSA), -chymotrypsin and cytochrome-C). Avidin is a model of a very stable hard protein. As most surfaces are negative, we considered preferably positive proteins at neutral pH, to check the surface passivation with respect to protein adsorption. It should be borne in mind however that the ionic strength of PBS buffer is not small with 0.15 M NaCl. Conversely the negative BSA can be viewed as a soft protein model, able to be adsorbed and denatured on many materials whatever their charge, thus a good candidate to check for possible hydrophobic interactions with surfaces. Indeed, this protein is often used in blocking buffers to prevent subsequent nonspecific adsorption.The protein-repellent character of the PL-PMHS(20 nm) surface was checked in the configuration of flowing solutions in a slit. No adsorption of -chymotrypsin and cytochrome-C was observed (Fig.3a).

A c c e p t e d M a n u s c r i p t 16 Figure 3 1 ±0. 9

 16319 Figure 3 Adsorption under laminar flow conditions with wall shear rate = 1000 s -1 . Closed

Figure 4

 4 Figure 4 Characterization of liposomes and of their interaction with surfaces. (top) Photon

A c c e p t e d M a n u s c r i p t 20 Scheme 1

 201 Scheme 1 Grafting reaction of Alexa, sketched as a big sphere, to surface silanols. (top) via

Figure 1

 1 Figure 1 Method of surface treatment and physico-chemical characteristics of the films. (a)

Figure 2

 2 Figure 2 Characterization of the films by atomic force microscopy. AFM pictures (5 µm × 5 µm) of PMHS layers (thickness h) and of their derived PL-PMHS layers. Corresponding

Figure 3

 3 Figure 3 Adsorption in laminar flow conditions with wall shear rate = 1000 s -1 . Closed

Acknowledgments This work was especially supported by FP7 European grant NMP-214538 (BISNES project; Coord. D. Nicolau). We are grateful to M. Ramonda (LMCP, UM2) for the AFM pictures, to Valérie Flaud (XPS technological Platform, UM2) for XPS spectra and to F. Pichot (UM2) for access to clean room and ellipsometry.

-Simple method to build a thin phospholipid layer covalently linked to a polymer network -From phospholipids, building of a stable background dense layer of phosphorylcholine heads.

-Possibilities of additional routine chemistry for functionnalization over the phosphorylcholine background.


Joël Ouaknine

Amaury Pouly

João Sousa-Pinto

James Worrell

On the decidability of membership in matrix-exponential semigroups

Keywords: CCS Concepts:, Theory of computation → Timed and hybrid models; linear forms in logarithms, matrix exponential, matrix reachability, matrix logarithms, commuting matrices, hybrid automata

We consider the decidability of the membership problem for matrix-exponential semigroups: given 𝑘 ∈ N and square matrices 𝐴 1 , . . . , 𝐴 𝑘 , 𝐶, all of the same dimension and with real algebraic entries, decide whether 𝐶 is contained in the semigroup generated by the matrix exponentials exp(𝐴 𝑖 𝑡), where 𝑖 ∈ {1, . . . , 𝑘 } and 𝑡 ≥ 0. This problem can be seen as a continuous analog of Babai et al.'s and Cai et al.'s problem of solving multiplicative matrix equations, and has applications to reachability analysis of linear hybrid automata and switching systems. Our main results are that the semigroup membership problem is undecidable in general, but decidable if we assume that 𝐴 1 , . . . , 𝐴 𝑘 commute. The decidability proof is by reduction to a version of integer programming that has transcendental constants. We give a decision procedure for the latter using Baker's theorem on linear forms in logarithms of algebraic numbers, among other tools. The undecidability result is shown by reduction from Hilbert's Tenth Problem.

INTRODUCTION

Reachability problems are a staple of theoretical computer science and algorithmic verification. In this paper, our motivation stems from systems with both continuous variables and discrete control modes. Systems of this type permeate engineering and the physical sciences: examples include linear hybrid automata, switching systems, continuous-time Markov chains, and cyber-physical systems-see [START_REF] Alur | Principles of Cyber-Physical Systems[END_REF][START_REF] Asarin | Low dimensional hybrid systems -decidable, undecidable, don't know[END_REF][START_REF] Henzinger | The theory of hybrid automata[END_REF][START_REF] Henzinger | What's decidable about hybrid automata?[END_REF].

We focus on systems consisting of a finite number of discrete control modes (or states), having the property that the continuous variables of interest evolve in each mode according to some linear differential equation of the form 𝒙 = 𝐴𝒙. Here 𝒙 is a vector of continuous variables, and 𝐴 is a square 'rate' matrix of appropriate dimension. As is well-known, in each mode the closed form solution 𝒙 (𝑡) to the differential equation admits a matrix-exponential representation of the form 𝒙 (𝑡) = exp(𝐴𝑡)𝒙 (0). Thus if such a system evolves through a series of 𝑘 modes, where the 𝑖-th mode has rate matrix 𝐴 𝑖 , then the overall effect on the initial configuration 𝒙 (0) is determined by multiplying by the matrix 𝑘 𝑖=1 exp(𝐴 𝑖 𝑡 𝑖 ), where 𝑡 𝑖 ≥ 0 denotes the amount of time spent in the 𝑖-th mode for 𝑖 = 1, . . . , 𝑘. A particularly interesting situation arises when the matrices 𝐴 𝑖 commute; in such cases the order in which the modes are visited (or indeed whether they are visited only once or several times) is immaterial, the only relevant data being the total time spent in each mode. Natural questions then arise as to what kinds of linear transformations can thus be achieved by such systems.

The following decision problem captures a fundamental reachability question in the setting described above. The Matrix-Exponential Semigroup Membership Problem (MSMP) asks, given square matrices 𝐴 1 , . . . , 𝐴 𝑘 , 𝐶, all of the same dimension and with real-algebraic entries, whether 𝐶 is a member of the matrix semigroup generated by the set of matrices exp(𝐴 𝑖 𝑡) for 𝑖 ∈ {1, . . . , 𝑘 } and 𝑡 ≥ 0. The main result of this paper shows decidability of this problem when the matrices 𝐴 1 , . . . , 𝐴 𝑘 commute. We also show that the problem is undecidable in general.

Related Work

In the case of matrix-exponential semigroups with a single generator, the membership problem was shown to be decidable in [START_REF] Hainry | Reachability in linear dynamical systems[END_REF] and a polynomial-time procedure was subsequently given in [START_REF] Chen | Continuous-time orbit problems are decidable in polynomial-time[END_REF]. Further reachability problems in the setting of a single generator are considered in [START_REF] Bell | The continuous Skolem-Pisot problem[END_REF].

There is a rich literature on membership problems for matrix semigroups, which can be seen as discrete analogs of the matrix-exponential semigroups studied in this paper. Given square matrices 𝐴 1 , . . . , 𝐴 𝑘 , 𝐶, all of the same dimension, and with algebraic entries, the Matrix Semigroup Membership Problem consists in deciding whether the matrix 𝐶 belongs to the multiplicative semigroup generated by {𝐴 1 , . . . , 𝐴 𝑘 }. A related problem is to determine, given the multiplicative matrix equation 𝑘 𝑖=1 𝐴 𝑛 𝑖 𝑖 = 𝐶, whether there is a solution 𝑛 1 , . . . , 𝑛 𝑘 ∈ N. Both these problems have been shown to be undecidable in general [START_REF] Bell | Matrix equations and Hilbert's Tenth Problem[END_REF][START_REF] Paterson | Undecidability in 3 × 3 matrices[END_REF]. When the matrices 𝐴 1 , . . . , 𝐴 𝑘 commute, the two problems are equivalent, and known to be decidable [START_REF] Babai | Multiplicative equations over commuting matrices[END_REF]. Prior to [START_REF] Babai | Multiplicative equations over commuting matrices[END_REF], the case 𝑘 = 1 was shown to be decidable in [START_REF] Kannan | Polynomial-time algorithm for the orbit problem[END_REF] and the case 𝑘 = 2 was first shown to be decidable in [START_REF] Cai | The complexity of the A B C problem[END_REF]. The case 𝑘 = 2 without commutativity assumptions was shown to be decidable in [START_REF] Bell | Matrix equations and Hilbert's Tenth Problem[END_REF]. See [START_REF] Halava | Decidable and undecidable problems in matrix theory[END_REF] for a relevant survey, and [START_REF] Choffrut | Some decision problems on integer matrices[END_REF] for some interesting related problems.

Structure of the Paper

In order to prove decidability of the Matrix-Exponential Semigroup Membership Problem in case the generating matrices 𝐴 1 , . . . , 𝐴 𝑘 all commute, we successively reformulate the problem until we eventually arrive at a version of integer programming that has transcendental constants. We show how to solve the latter problem using Baker's theorem on linear forms in logarithms of algebraic numbers and results in simultaneous Diophantine approximation.

If matrices 𝐴 and 𝐵 commute, then so do their exponentials exp(𝐴) and exp(𝐵). Using this fact it immediately follows that in the case of commuting matrices 𝐴 1 , . . . , 𝐴 𝑘 , the Matrix-Exponential Semigroup Membership Problem is equivalent to the following problem: Definition 1.1. Given square matrices 𝐴 1 , . . . , 𝐴 𝑘 and 𝐶, all of the same dimension and with real algebraic entries, the Matrix-Exponential Equation Problem (MEP) consists in determining whether there exist real numbers 𝑡 1 , . . . , 𝑡 𝑘 ≥ 0 such that 𝑘 𝑖=1 exp(𝐴 𝑖 𝑡 𝑖 ) = 𝐶.

The Matrix-Exponential Equation Problem corresponds to reachability in a switching system in which the number of mode switches is fixed a priori. Using results in linear algebra about commuting matrices and basic facts about matrix logarithms, the special case of the Matrix-Exponential Equation Problem for commuting matrices can be reduced to the following problem concerning systems of linear-exponential equations: Definition 1.2. An instance of the Linear-Exponential Equation Problem (LEP) consists of a system of linear-exponential equations in nonnegative real variables 𝑡 1 , . . . , 𝑡 𝑘 :

exp 𝑘 𝑖=1 𝜆 ( 𝑗) 𝑖 𝑡 𝑖 = 𝑐 𝑗 exp(𝑑 𝑗 ) ( 𝑗 = 1, . . . , 𝑚) 𝐴𝒕 = 𝒃 , (1)
where 𝑘, 𝑚 ∈ N and the constants 𝜆 ( 𝑗) 𝑖 , 𝑐 𝑗 , 𝑑 𝑗 and the entries of the matrix 𝐴 and vector 𝒃 are (possibly complex) algebraic numbers. The problem asks to determine whether there exist nonnegative real numbers 𝑡 1 , . . . , 𝑡 𝑘 ≥ 0 that satisfy the system [START_REF] Alur | Principles of Cyber-Physical Systems[END_REF].

By taking logarithms we can reduce the Linear-Exponential Equation Problem to a version of integer programming with transcendental constants. More precisely, we consider real constants that can be written as linear forms in logarithms of algebraic numbers, that is, numbers of the form 𝛼 0 + 𝑚 𝑖=1 𝛼 𝑖 log(𝛽 𝑖 ), where 𝛼 0 , . . . , 𝛼 𝑚 are algebraic numbers and 𝛽 1 , . . . , 𝛽 𝑚 are non-zero algebraic numbers (with both the 𝛼 𝑖 and 𝛽 𝑖 being possibly complex) and log is a fixed branch of the complex logarithm function.

Definition 1.3. An instance of the Algebraic-Logarithmic Integer Programming Problem (ALIP) consists of a finite system of inequalities of the form 𝜋Λ𝒙 ≤ 𝒆, where Λ is a matrix with real algebraic entries and where the coordinates of 𝒆 are real linear forms in logarithms of algebraic numbers. The problem asks to determine whether such a system admits a solution 𝒙 in integers.

Our strategy to decide the Matrix-Exponential Semigroup Membership Problem in the commutative case is to establish the following chain of reductions MSMP ≡ MEP ≤ LEP ≤ ALIP and finally to show decidability of ALIP using results in transcendence theory and Diophantine approximation.

In the general setting (i.e., without assuming commutativity) we show that both the Matrix-Exponential Semigroup Membership Problem and the Matrix-Exponential Equation Problem are undecidable. The proof is by reduction from Hilbert's Tenth Problem. We also show undecidability of variants of these problems that involve vector reachability and hyperplane reachability. Definition 1.4. Given square matrices 𝐴 1 , . . . , 𝐴 𝑘 and vectors 𝒙, 𝒚, all of the same dimension and with real algebraic entries, the Matrix-Exponential Vector Reachability Problem (MVRP) consists in deciding whether there exists a matrix 𝐶 in the semigroup generated by the set {exp(𝐴 𝑖 𝑡) : 𝑡 ≥ 0, 𝑖 = 1, . . . , 𝑘 } such that 𝐶𝒙 = 𝒚. The Matrix-Exponential Hyperplane Reachability Problem (MHRP) asks whether there exists such a matrix 𝐶 satisfying 𝒙 𝑇 𝐶𝒚 = 0.

Our undecidability results will be established by the following chain of reductions (where HTP refers to Hilbert's Tenth Problem):

HTP ≤ MEP ≤ MSMP ≤ MVRP ≤ MHRP .

MATHEMATICAL BACKGROUND

In this section we review some results in linear algebra, convex geometry, and number theory. We also introduce some specialised mathematical notation that will be needed in the subsequent development.

Linear Algebra

2.1.1 Jordan Canonical Forms. Let 𝐴 ∈ Q 𝑑×𝑑 be a square matrix with rational entries. The minimal polynomial of 𝐴 is the unique monic polynomial 𝑚(𝑥) ∈ Q[𝑥] of least degree such that 𝑚(𝐴) = 0. By the Cayley-Hamilton Theorem, the degree of 𝑚 is at most the dimension of 𝐴. The set 𝜎 (𝐴) of eigenvalues is the set of zeros of 𝑚, also known as the spectrum of 𝐴. The index of an eigenvalue 𝜆, denoted by 𝜈 (𝜆), is its multiplicity as a zero of 𝑚. We use 𝜈 (𝐴) to denote max 𝜆 ∈𝜎 (𝐴) 𝜈 (𝜆): the maximum index over all eigenvalues of 𝐴. An eigenvalue 𝜆 is said to be simple if 𝜈 (𝜆) = 1 and repeated otherwise. Given an eigenvalue 𝜆 ∈ 𝜎 (𝐴), we say that 𝒗 ∈ C 𝑑 is a generalised eigenvector of 𝐴 if 𝒗 ∈ ker (𝐴 -𝜆𝐼 ) 𝑚 , for some 𝑚 ∈ N.

For each eigenvalue 𝜆 of 𝐴, we denote the subspace of C 𝑑 spanned by the set of generalised eigenvectors associated with 𝜆 by V 𝜆 . We denote the subspace of C 𝑑 spanned by the set of generalised eigenvectors associated with some real eigenvalue by V 𝑟 . We likewise denote the subspace of C 𝑑 spanned by the set of generalised eigenvectors associated with some non-real eigenvalue by V 𝑐 .

Based on the Jordan decomposition of 𝐴, as described later on in this subsection, each vector 𝒗 ∈ C 𝑑 can be written uniquely as

𝒗 = ∑ 𝜆 ∈𝜎 (𝐴) 𝒗 𝜆 , (2)
where 𝒗 𝜆 ∈ V 𝜆 . It follows that 𝒗 can also be uniquely written as 𝒗 = 𝒗 𝑟 + 𝒗 𝑐 , where 𝒗 𝑟 ∈ V 𝑟 and 𝒗 𝑐 ∈ V 𝑐 . We will need the following result:

0 = 𝒗 -𝒗 = ∑ 𝜆 ∈𝜎 (𝐴) (𝒗 𝜆 -𝒗 𝜆 )
and from uniqueness of the decomposition [START_REF] Asarin | Low dimensional hybrid systems -decidable, undecidable, don't know[END_REF]. □

We can write any matrix 𝐴 ∈ C 𝑑×𝑑 as 𝐴 = 𝑄 -1 𝐽𝑄 for some invertible matrix 𝑄 and block diagonal Jordan matrix 𝐽 = diag(𝐽 1 , . . . , 𝐽 𝑁 ), with each block 𝐽 𝑖 having the following form:

𝜆 1 0 • • • 0 0 𝜆 1 • • • 0 . . . . . . . . . . . . . . . 0 0 0 • • • 1 0 0 0 • • • 𝜆
Moreover, given a rational matrix 𝐴, its Jordan Normal Form 𝐴 = 𝑄 -1 𝐽𝑄 can be computed in polynomial time, as shown in [START_REF] Cai | Computing Jordan normal forms exactly for commuting matrices in polynomial time[END_REF]. Note that each vector 𝒗 appearing as a column of the matrix 𝑄 -1 is a generalised eigenvector, and that the index 𝜈 (𝜆) of each eigenvalue 𝜆 corresponds to the dimension of the largest Jordan block associated with it.

On the decidability of membership in matrix-exponential semigroups :5

One can obtain a closed-form expression for powers of block diagonal Jordan matrices, and use this to get a closed-form expression for the powers of a general matrix 𝐴. In fact, if 𝐽 𝑖 is a 𝑙 × 𝑙 Jordan block associated with an eigenvalue 𝜆, then

𝐽 𝑛 𝑖 = 𝜆 𝑛 𝑛𝜆 𝑛-1 𝑛 2 𝜆 𝑛-1 • • • 𝑛 𝑙-1 𝜆 𝑛-𝑙+1 0 𝜆 𝑛 𝑛𝜆 𝑛-1 • • • 𝑛 𝑙-2 𝜆 𝑛-𝑙+2 . . . . . . . . . . . . . . . 0 0 0 • • • 𝑛𝜆 𝑛-1 0 0 0 • • • 𝜆 𝑛 (3)
where 𝑛 𝑗 is defined to be 0 when 𝑛 < 𝑗. 2.1.2 Matrix exponentials. The exponential of a matrix 𝐴 ∈ C 𝑑×𝑑 is defined by the power series

exp(𝐴) := ∞ ∑ 𝑖=0 𝐴 𝑖 𝑖! ∈ C 𝑑×𝑑 .
The series above always converges, and so the exponential of a matrix is always well defined. Given 𝑡 ∈ C, one can obtain a closed-form representation of exp(𝐴𝑡) as follows. Find 𝑄 ∈ GL 𝑑 (C) such that 𝐴 = 𝑄 -1 𝐽𝑄 and 𝐽 = diag(𝐽 1 , . . . , 𝐽 𝑁 ) is a block diagonal Jordan matrix. Then exp(𝐴𝑡) = 𝑄 -1 exp(𝐽𝑡)𝑄, where exp(𝐽𝑡) = diag(exp(𝐽 1 𝑡), . . . , exp(𝐽 𝑁 𝑡)). Note that due to Equation (3), if

𝐽 = 𝜆 1 0 • • • 0 0 𝜆 1 • • • 0 . . . . . . . . . . . . . . . 0 0 • • • 𝜆 1 0 0 • • • 0 𝜆
is a Jordan block associated with an eigenvalue 𝜆, then exp(𝐽𝑡) = exp(𝜆𝑡)

1 𝑡 𝑡 2 2 • • • 𝑡 𝑘-1 (𝑘-1)! 0 1 𝑡 • • • 𝑡 𝑘-2 (𝑘-2)! . . . . . . . . . . . . . . . 0 0 • • • 1 𝑡 0 0 • • • 0 1
.

If 𝐴 and 𝐵 commute then so do exp(𝐴) and exp(𝐵) and in this case we have exp (𝐴) exp (𝐵) = exp (𝐴 + 𝐵). Proposition 2.2. Let 𝒗 lie in the generalised eigenspace V 𝜆 for some 𝜆 ∈ 𝜎 (𝐴). Then 𝒃 𝑇 exp(𝐴𝑡)𝒗 is a linear combination of terms of the form 𝑡 𝑛 exp(𝜆𝑡), 𝑛 ∈ N.

Proof. Note that, if 𝐴 = 𝑄 -1 𝐽𝑄 and 𝐽 = diag(𝐽 1 , . . . , 𝐽 𝑁 ) is a block diagonal Jordan matrix, then exp(𝐴𝑡) = 𝑄 -1 exp(𝐽𝑡)𝑄 and exp(𝐽𝑡) = diag(exp(𝐽 1 𝑡), . . . , exp(𝐽 𝑁 𝑡)). The result follows by observing that 𝑄𝒗 is zero in every component other than those pertaining the block corresponding to the eigenspace V 𝜆 . whenever the above series converges. In particular the matrix logarithm is well-defined in case 𝐴 is unipotent (e.g., when 𝐴 is a upper unitriangular matrix) since in this case above series becomes a polynomial expression in 𝐴. In fact it is well-known that the matrix exponential function and matrix logarithm functions yield a bijection between nilpotent and unipotent matrices in C 𝑑×𝑑 (see, e.g., [START_REF] Hall | Lie Groups, Lie Algebras, and Representations[END_REF]Chapter 2]). Thus we have: Proposition 2.3. Given an upper unitriangular matrix 𝑀 ∈ C 𝑑×𝑑 , there exists a unique strictly upper triangular matrix 𝐿 such that exp(𝐿) = 𝑀. Moreover, the entries of 𝐿 lie in the field Q(𝑀 𝑖,𝑗 : 1 ≤ 𝑖, 𝑗 ≤ 𝑑) generated over Q by the entries of 𝑀.

V 𝝀 = 𝑘 𝑖=1 ker (𝐴 𝑖 -𝜆 𝑖 𝐼 ) 𝑑 . Let Σ = {𝝀 ∈ 𝜎 (𝐴 1 ) × • • • × 𝜎 (𝐴 𝑘 ) : V 𝝀 ≠ {0}}.
Below, 𝐴 𝑖 ↾ V 𝝀 denotes the restriction of the linear operator 𝐴 𝑖 to the linear subspace V 𝝀 , which is invariant under 𝐴 𝑖 .

Theorem 2.4. For all 𝝀 = (𝜆 1 , . . . , 𝜆 𝑘 ) ∈ Σ and all 𝑖 ∈ {1, . . . , 𝑘 } the following properties hold:

(1) V 𝝀 is invariant under 𝐴 𝑖 .

(

) 𝜎 (𝐴 𝑖 ↾ V 𝝀 ) = {𝜆 𝑖 }. ( 2
) C 𝑑 = 𝝀 ∈Σ V 𝝀 . 3
Proof. We show by induction on 𝑘 that the subspaces V 𝝀 satisfy the properties above. When 𝑘 = 1, the result follows from the existence of Jordan Canonical Forms. When 𝑘 > 1, suppose that 𝜎 (𝐴 𝑘 ) = {𝜇 1 , . . . , 𝜇 𝑚 }, and let U 𝑗 = ker (𝐴 𝑘 -𝜇 𝑗 𝐼 ) 𝑑 , for 𝑗 ∈ {1, . . . , 𝑚}. Again, it follows from the existence of Jordan Canonical Forms that

C 𝑑 = 𝑚 𝑗=1 U 𝑚 .
Pick 𝑖 ∈ {1, . . . , 𝑘 -1} and 𝑗 ∈ {1, . . . , 𝑚}. Now, as 𝐴 𝑘 and 𝐴 𝑖 commute, so do (𝐴 𝑘 -𝜇 𝑗 𝐼 ) and 𝐴 𝑖 . Therefore, for all

𝒗 ∈ U 𝑗 , (𝐴 𝑘 -𝜇 𝑗 𝐼 ) 𝑑 𝐴 𝑖 𝒗 = 𝐴 𝑖 (𝐴 -𝜇 𝑗 𝐼 ) 𝑑 𝒗 = 0, so 𝐴 𝑖 𝒗 ∈ U 𝑗 , that is, U 𝑗 is invariant under 𝐴 𝑖 .
The result follows from applying the induction hypothesis to the commuting operators 𝐴 𝑖 ↾ U 𝑗 . □

We will also make use of the following well-known result on simultaneous triangularisation of commuting matrices. See, for example, [START_REF] Newman | Two classical theorems on commuting matrices[END_REF]. Theorem 2.5. Given commuting matrices 𝐴 1 , . . . , 𝐴 𝑘 ∈ C 𝑑×𝑑 , there exists a matrix 𝑃 ∈ GL 𝑑 (C) such that 𝑃 -1 𝐴 𝑖 𝑃 is upper triangular for all 𝑖 ∈ {1, . . . , 𝑘 }. Moreover if the entries of every matrix 𝐴 𝑖 are algebraic numbers then 𝑃 may be chosen to have algebraic entries also.

Note that Theorem 2.5 will allow us to reduce general instances of MSMP with commuting matrices to the subcase where all those matrices are in upper triangular form.

On the decidability of membership in matrix-exponential semigroups :7

Number Theory

Linear diophantine equations with algebraic coefficients.

A complex number 𝛼 is said to be algebraic if it is a root of some non-zero polynomial with integer coefficients. The set of algebraic numbers forms a field, denoted Q. A complex number that is not algebraic is said to be transcendental.

For computational purposes we represent an algebraic number by a polynomial 𝑃 with rational coefficients such that 𝑃 (𝛼) = 0, together with a numerical approximation 𝑝 + 𝑞𝑖, where 𝑝, 𝑞 ∈ Q, of sufficient accuracy to distinguish 𝛼 from the other roots of 𝑃 [START_REF] Cohen | A Course in Computational Algebraic Number Theory[END_REF]Section 4.2.1]. Under this representation, arithmetic operations and equality testing can be carried out effectively, as can sign testing of real algebraic numbers

The subfield K of C generated by given algebraic numbers 𝛼 1 , . . . , 𝛼 𝑘 is finite dimensional as a vector space over Q. Moreover, given representations of 𝛼 1 , . . . , 𝛼 𝑘 , one can compute a basis of K over Q and the (rational) coefficients of each 𝛼 𝑖 with respect to this basis (see [START_REF] Cohen | A Course in Computational Algebraic Number Theory[END_REF]Section 4.5]). Proposition 2.6. Let 𝑆 = {𝒙 ∈ Z 𝑛 : 𝐴𝒙 = 𝒃}, where matrix 𝐴 and vector 𝒃 have algebraic coefficients. Then we can decide whether 𝑆 is non-empty and, if so, can compute 𝒙 0 ∈ Z 𝑑 and 𝑀 ∈ Z 𝑑×𝑠 , for some 𝑠 ≤ 𝑑, such that 𝑆 = {𝒙 0 + 𝑀𝒚 : 𝒚 ∈ Z 𝑠 }.

Proof. Compute a basis 𝛼 1 , . . . , 𝛼 𝑘 of the subfield of C that is generated by the entries of 𝐴 and 𝒃. Then we can write 𝐴 = 𝑘 𝑖=1 𝐴 𝑖 𝛼 𝑖 and 𝒃 = 𝑘 𝑖=1 𝒃 𝑖 𝛼 𝑖 , where 𝐴 𝑖 is a matrix of rational numbers of the same dimension as 𝐴, and 𝒃 𝑖 is a rational vector of the same dimension as 𝒃. Now we have that

𝐴𝒙 = 𝒃 ⇔ 𝑘 ∑ 𝑖=1 𝐴 𝑖 𝛼 𝑖 𝒙 = 𝑘 ∑ 𝑖=1 𝒃 𝑖 𝛼 𝑖 ⇔ 𝐴 𝑖 𝒙 = 𝒃 𝑖 , ∀𝑖 ∈ {1, . . . , 𝑘 }.
Thus we have characterised 𝑆 as the set of integer solutions of a system of equations with rational coefficients. Now the desired representation of 𝑆 can be computed using, e.g., the the procedure described in [START_REF] Cohen | A Course in Computational Algebraic Number Theory[END_REF]Chapter X]. □ 2.2.2 Linear Forms in Logarithms. Let log denote the principal branch of the complex logarithm function, i.e., the imaginary part of log(𝑧) lies in the interval (-𝜋, 𝜋] for all 𝑧 ≠ 0.

Given 𝑘 ∈ N, a number Λ of the form

Λ := 𝛼 0 + 𝛼 1 log(𝛽 1 ) + • • • + 𝛼 𝑘 log(𝛽 𝑘 ), (4)
where 𝛼 0 , . . . , 𝛼 𝑛 , 𝛽 1 , . . . , 𝛽 𝑘 are algebraic numbers, with the 𝛽 𝑖 non-zero, is said to be a linear form in logarithms of algebraic numbers. Note that the collection of such linear forms is closed under addition, complex conjugation, and under multiplication by algebraic numbers.

In order to effectively manipulate linear forms we will need the following result of Baker [START_REF] Baker | Transcendental Number Theory[END_REF].

Theorem 2.7 (Baker). Let 𝛽 1 , . . . , 𝛽 𝑘 be non-zero algebraic numbers. If log(𝛽 1 ), . . . , log(𝛽 𝑘 ) are linearly independent over Q, then 1, log(𝛽 1 ), . . . , log(𝛽 𝑘 ) are linearly independent over Q. Proposition 2.8. Let Λ = 𝛼 0 + 𝑘 𝑖=1 𝛼 𝑖 log(𝛽 𝑖 ) ∈ R be a linear form in logarithms of algebraic numbers for some nonnegative integer 𝑘. Then we can effectively determine the sign of Λ (zero, positive, or negative) and whether Λ 𝜋 is algebraic. Proof. Clearly we may assume without loss of generality that 𝛼 1 , . . . , 𝛼 𝑘 are non-zero. We say that Λ is reduced if the set of terms T Λ := {log(-1), log(𝛽 1 ), . . . , log(𝛽 𝑘 )} is linearly independent over Q. Rational linear independence of T Λ is equivalent to the requirement that the set of multiplicative relations

L := {(𝑛 1 , . . . , 𝑛 𝑘 ) ∈ Z 𝑘 : 𝛽 𝑛 1 1 • • • 𝛽 𝑛 𝑘 𝑘 =
1} contain only the zero vector. Now L is a subgroup of Z 𝑘 and by a deep result of Masser [START_REF] Masser | Linear relations on algebraic groups[END_REF] it is possible to compute a basis of L (see, e.g., [START_REF] Cai | The complexity of the A B C problem[END_REF]). In particular, if Λ is not reduced then we can compute an integer linear relation among log(-1), log(𝛽 1 ), . . . , log(𝛽 𝑘 ) and rewrite Λ so as to eliminate one of the terms log(𝛽 𝑖 ) in T Λ . Continuing in this way we eventually reach an equivalent reduced form of Λ. Suppose that Λ is reduced. Then by Theorem 2.7 the set {1, log(-1), log(𝛽 1 ), . . . , log(𝛽 𝑘 )} is linearly independent over Q. It follows that Λ = 0 if and only if 𝑘 = 0 and 𝛼 0 = 0. Hence it is decidable whether or not Λ = 0. If Λ ≠ 0 then we can determine the sign of Λ by computing a rational approximation of Λ of sufficient precision. Furthermore we have that Λ/𝜋 ∈ Q if and only if 𝑘 = 1, 𝛼 0 = 0 and 𝛽 1 = -1. □ 2.2.3 Diophantine Approximation. Given a vector 𝒂 ∈ R 𝑑 and a set 𝑆 ⊆ R 𝑑 , write dist(𝒂, 𝑆) for the ℓ 1 -distance between 𝒂 and 𝑆, i.e., inf 𝒃 ∈𝑆 ∥𝒂 -𝒃 ∥ 1 . We will need the following consequence of Kronecker's theorem on simultaneous inhomogeneous diophantine approximation (see [START_REF] Khachiyan | Integer optimization on convex semialgebraic sets[END_REF]Corollary 2.8]). Theorem 2.9. Suppose that C = {𝒄 1 , . . . , 𝒄 𝑘 } ⊆ R 𝑑 and that no integer vector is orthogonal to C. Then for any 𝒒 ∈ R 𝑑 and for any 𝜀 > 0 there exist non-negative real numbers 𝜆 1 , . . . , 𝜆 𝑘 such that [START_REF] Lang | Introduction to Transcendental Number Theory[END_REF] is a unifying conjecture in transcendence theory that generalises many of the classical results in the field (including Theorem 2.7). The conjecture states that if 𝛼 1 , . . . , 𝛼 𝑘 ∈ C are rationally linearly independent then some 𝑘-element subset of {𝛼 1 , . . . , 𝛼 𝑘 , 𝑒 𝛼 1 , . . . , 𝑒 𝛼 𝑘 } is algebraically independent. Assuming Schanuel's Conjecture, MacIntyre and Wilkie [START_REF] Macintyre | On the decidability of the real exponential field[END_REF] have shown decidability of the first-order theory of the expansion of the real field with the exponentiation function and the sin and cos functions restricted to bounded intervals. Theorem 2.10 (Wilkie and MacIntyre). If Schanuel's conjecture is true, then, for each 𝑛 ∈ N, the first-order theory of the strucure (R, +, •, exp, cos ↾ [0,𝑛] , sin ↾ [0,𝑛] ) is decidable.

dist 𝒒 + 𝑘 ∑ 𝑖=1 𝜆 𝑖 𝒄 𝑖 , Z 𝑑 ≤ 𝜀 . 2.2.4 Schanuel's Conjecture. Schanuel's Conjecture

Convex Geometry

Convex Polytopes.

A convex polytope is a subset of R 𝑛 of the form

P = {𝒙 ∈ R 𝑛 : 𝐴𝒙 ≤ 𝒃},
where 𝐴 ∈ R 𝑑×𝑛 and 𝒃 ∈ R 𝑑 for some 𝑑 ∈ N. When all the entries of 𝐴 and 𝒃 are algebraic numbers, P is said to have an algebraic description. In this case we can decide non-emptiness of P, e.g., by reduction to the satisfiability problem for the existential theory of real closed fields.

We will need the following result:

Theorem 2.11 (Minkowski-Weyl). Any polytope P ⊆ R 𝑑 can be written as the sum of two sets H ⊆ R 𝑑 and C ⊆ R 𝑑 , where H is a finitely generated convex hull and C is a finitely generated cone.

Fourier-Motzkin Elimination.

Fourier-Motzkin elimination is a simple method for eliminating variables from systems of linear inequalities. The procedure consists in isolating one variable at a time and comparing all its lower and upper bounds. Note that this method preserves the set of solutions on the remaining variables, so a solution of the reduced system can always be extended to a solution of the original one. Proposition 2.12. It is decidable whether a given convex polytope P = {𝒙 ∈ R 𝑛 : 𝜋𝐴𝒙 < 𝒃} is empty, where the entries of 𝐴 are all real algebraic numbers and those of 𝒃 are real linear forms in logarithms of algebraic numbers. Moreover, if P is non-empty then one can compute a rational vector 𝒒 ∈ P.

Proof. Note that P is non-empty iff there exists 𝒚 ∈ R 𝑛 with 𝐴𝒚 < 𝒃. The existence of such a vector 𝒚 can be decided using Fourier-Motzkin elimination. The linear inequalities that are generated by the elimination process are such that each coefficient of a variable 𝑦 𝑖 is real algebraic and the constant term is a real linear form in logarithms of algebraic numbers. Having eliminated all variables we can decide emptiness since we can effectively decide whether a real linear form in logarithms is strictly positive by Proposition 2.8. □

EXAMPLE

The following example illustrates some elements of our approach to establishing decidability of the Matrix-Exponential Semigroup Membership Problem.

Let 𝜆 1 , 𝜆 2 be real algebraic numbers such that 𝜆 1 > 𝜆 2 and consider the following commuting matrices 𝐴 1 , 𝐴 2 :

𝐴 𝑖 = 𝜆 𝑖 1 0 𝜆 𝑖 , 𝑖 ∈ {1, 2}.
Given nonnegative real variables 𝑡 1 , 𝑡 2 we have that (see Section 2.1.2):

exp(𝐴 𝑖 𝑡 𝑖 ) = exp(𝜆 𝑖 𝑡 𝑖 ) 1 𝑡 𝑖 0 1 , 𝑖 ∈ {1, 2}. (5)
Let 𝑐 1 , 𝑐 2 be real algebraic numbers such that 𝑐 1 , 𝑐 2 > 0, and let

𝐶 = 𝑐 1 𝑐 2 0 𝑐 1 .
We would like to determine whether there exist

𝑡 1 , 𝑡 2 ∈ R, 𝑡 1 , 𝑡 2 ≥ 0 such that exp(𝐴 1 𝑡 1 ) exp(𝐴 2 𝑡 2 ) = 𝐶. (6)
Using the closed-form expression for matrix exponentials in (5), Equation ( 6) is equivalent to the following pair of equations:

exp(𝜆 1 𝑡 1 + 𝜆 2 𝑡 2 ) = 𝑐 1 (𝑡 1 + 𝑡 2 ) exp(𝜆 1 𝑡 1 + 𝜆 2 𝑡 2 ) = 𝑐 2 .
Solving directly, we have

𝑡 1 = log(𝑐 1 ) -𝑐 2 𝑐 1 𝜆 2 𝜆 1 -𝜆 2 and 𝑡 2 = 𝑐 2 𝑐 1 𝜆 1 -log(𝑐 1 ) 𝜆 1 -𝜆 2 . Now 𝑡 1 , 𝑡 2 ≥ 0 holds if and only if 𝜆 2 ≤ 𝑐 1 𝑐 2 log(𝑐 1 ) ≤ 𝜆 1 .
Whether these inequalities hold amounts to comparing linear forms in logarithms of algebraic numbers, which is decidable by Proposition 2.8.

We first reduce the Matrix-Exponential Equation Problem (MEP) with commuting matrices to the Linear-Exponential Problem (LEP), as defined in Section 1.2. The idea is to perform a change of basis so that the matrices 𝐴 1 , . . . , 𝐴 𝑘 , and 𝐶 in an instance of MEP all become block-diagonal, with each block being upper triangular; we then analyse the problem block-wise, making use of Proposition 2.3 concerning logarithms of unipotent matrices.

Proposition 4.1. MEP with commuting matrices reduces to LEP .

Proof. Consider an instance of MEP, as given in Definition 1.1, with commuting 𝑛 × 𝑛 matrices 𝐴 1 , . . . , 𝐴 𝑘 and target matrix 𝐶.

We first show how to define a matrix 𝑃 such that each matrix 𝑃 -1 𝐴 𝑖 𝑃 is block diagonal, for 𝑖 = 1, . . . , 𝑘, with each block being upper triangular.

By Theorem 2.4 we can write C 𝑛 as a direct sum of subspaces C 𝑛 = ⊕ 𝑚 𝑗=1 V 𝑗 such that for every subspace V 𝑗 and matrix 𝐴 𝑖 , V 𝑗 is an invariant subspace of 𝐴 𝑖 on which 𝐴 𝑖 has a single eigenvalue 𝜆 ( 𝑗) 𝑖 . Define a matrix 𝑄 by picking an algebraic basis for each V 𝑗 and taking the columns of 𝑄 to be the successive vectors of each basis. Then for 𝑖 = 1, . . . , 𝑘 the matrix 𝑄 -1 𝐴 𝑖 𝑄 is block-diagonal, where the 𝑗-th block is a matrix 𝐵 ( 𝑗) 𝑖 that represents 𝐴 𝑖 ↾ V 𝑗 , 𝑗 = 1, . . . , 𝑚. Fixing the index of a block 𝑗 ∈ {1, . . . , 𝑚}, note that the matrices 𝐵 ( 𝑗) 1 , . . . , 𝐵 ( 𝑗) 𝑘 all commute. Thus we may apply Theorem 2.5 to obtain an algebraic matrix 𝑀 𝑗 such that each matrix 𝑀 -1 𝑗 𝐵 ( 𝑗) 𝑖 𝑀 𝑗 is upper triangular, 𝑖 = 1, . . . , 𝑘. Thus we can write

𝑀 -1 𝑗 𝐵 ( 𝑗) 𝑖 𝑀 𝑗 = 𝜆 ( 𝑗) 𝑖 𝐼 + 𝑁 ( 𝑗)

𝑖

for some strictly upper triangular matrix 𝑁 ( 𝑗) 𝑖 . We define 𝑀 to be the block-diagonal matrix 𝑀 = diag(𝑀 1 , . . . , 𝑀 𝑚 ). Letting 𝑃 = 𝑄𝑀, we have that 𝑃 -1 𝐴 𝑖 𝑃 is block-diagonal, with the 𝑗-th block being 𝜆 ( 𝑗) 𝑖 𝐼 + 𝑁 ( 𝑗)

𝑖

for 𝑗 = 1, . . . , 𝑚. Now for all 𝑡 1 , . . . , 𝑡 -𝐾 ≥ 0 we have

𝑘 𝑖=1 exp (𝐴 𝑖 𝑡 𝑖 ) = 𝐶 ⇔ 𝑘 𝑖=1 exp 𝑃 -1 𝐴 𝑖 𝑃𝑡 𝑖 = 𝑃 -1 𝐶𝑃 . (7)
If 𝑃 -1 𝐶𝑃 is not block-diagonal, with each block being upper triangular and with the same entries along the diagonal, then Equation [START_REF] Cai | Computing Jordan normal forms exactly for commuting matrices in polynomial time[END_REF] has no solution and the problem instance must be negative. Otherwise, denoting the blocks of 𝑃 -1 𝐶𝑃 by 𝐷 ( 𝑗) for 𝑗 ∈ {1, . . . , 𝑚}, our problem amounts to simultaneously solving the system of matrix equations

𝑘 𝑖=1 exp 𝜆 ( 𝑗) 𝑖 𝐼 + 𝑁 ( 𝑗) 𝑖 𝑡 𝑖 = 𝐷 ( 𝑗) , 𝑗 ∈ {1, . . . , 𝑚} (8)
where there is one equation for each block.

For each fixed 𝑗, the matrices 𝑁 ( 𝑗) 𝑖 inherit commutativity from the matrices 𝐵 ( 𝑗) 𝑖 , so we have

𝑘 𝑖=1 exp (𝜆 ( 𝑗) 𝑖 𝐼 + 𝑁 ( 𝑗) 𝑖 )𝑡 𝑖 = exp 𝑘 ∑ 𝑖=1 (𝜆 ( 𝑗) 𝑖 𝐼 + 𝑁 ( 𝑗) 𝑖 )𝑡 𝑖 = exp 𝑘 ∑ 𝑖=1 𝜆 ( 𝑗) 𝑖 𝑡 𝑖 • exp 𝑘 ∑ 𝑖=1
On the decidability of membership in matrix-exponential semigroups :11

Hence the system ( 8) is equivalent to

exp 𝑘 ∑ 𝑖=1 𝜆 ( 𝑗) 𝑖 𝑡 𝑖 • exp 𝑘 ∑ 𝑖=1 𝑁 ( 𝑗) 𝑖 𝑡 𝑖 = 𝐷 ( 𝑗) 𝑗 ∈ {1, . . . , 𝑚} . (9)
By assumption, the diagonal entries of each matrix 𝐷 ( 𝑗) are all equal to a single value-say 𝑐 ( 𝑗) . Since the diagonal entries of exp 𝑘 𝑖=1 𝑁 ( 𝑗) 𝑡 𝑖 are all 1, the system ( 9) is equivalent to:

exp 𝑘 ∑ 𝑖=1 𝜆 ( 𝑗) 𝑖 𝑡 𝑖 = 𝑐 ( 𝑗) and exp 𝑘 ∑ 𝑖=1 𝑁 ( 𝑗) 𝑖 𝑡 𝑖 = 1 𝑐 ( 𝑗) 𝐷 ( 𝑗)
for 𝑗 = 1, . . . , 𝑚.

Applying Proposition 2.3, the above system can equivalently be written

exp 𝑘 ∑ 𝑖=1 𝜆 ( 𝑗) 𝑖 𝑡 𝑖 = 𝑐 ( 𝑗) and 𝑘 ∑ 𝑖=1 𝑁 ( 𝑗) 𝑖 𝑡 𝑖 = 𝑆 ( 𝑗) (10)
for some effectively computable matrices 𝑆 ( 𝑗) with algebraic entries, 𝑗 = 1, . . . , 𝑚. But the above system of equations is an instance of LEP. □

Next we reduce the Linear-Exponential Equation Problem to the Algebraic-Logarithmic Integer Programming Problem (ALIP), as defined in Section 1.2.

and linear equations 𝐴𝒕 = 𝒃.

Recall that log denotes the principal branch of the complex logarithm function. Note that if any 𝑐 𝑗 = 0 for some 𝑗 then [START_REF] Cohen | A Course in Computational Algebraic Number Theory[END_REF] has no solution. Otherwise, by applying log to each equation in [START_REF] Cohen | A Course in Computational Algebraic Number Theory[END_REF], we get

𝑘 ∑ ℓ=1 𝜆 ( 𝑗) ℓ 𝑡 ℓ = 𝑑 𝑗 + log(𝑐 𝑗 ) + 2𝜋𝑖𝑛 𝑗 𝑗 ∈ {1, . . . , 𝑚} (12)
where 𝑛 𝑗 ∈ Z.

The system of equations ( 12) can be written in matrix form as

Λ𝒕 ∈ 𝒅 + log(𝒄) + 2𝜋𝑖Z 𝑚 , ( 13
)
where Λ is the 𝑚 × 𝑘 matrix with Λ 𝑗,ℓ = 𝜆 ( 𝑗) ℓ and log is applied pointwise to vectors. A solution to the given instance of LEP comprises a solution 𝒕 ≥ 0 to (13) that furthermore satisfies 𝐴𝒕 = 𝒃. Such a solution exists if and only if the convex polytope T := {𝒙 ∈ R 𝑚 : ∃𝒕 ≥ 0 (𝒅 + log(𝒄) + 2𝜋𝑖𝒙 = Λ𝒕 and 𝐴𝒕 = 𝒃)} contains an integer point.

The linear constraints in the definition of T are such that the coefficients of 𝑡 1 , . . . , 𝑡 𝑘 are algebraic and the constant terms are linear forms in logarithms of algebraic numbers. By dividing the equational constraints in the definition of T into real and imaginary parts, we can use Fourier-Motzkin elimination to eliminate the existentially quantified variables 𝒕 and arrive at a characterisation T = {𝒙 : 𝜋𝐵𝒙 ≤ 𝒆}, for some effectively computable matrix 𝐵 and vector 𝒆 such that the entries of 𝐵 are real algebraic and the entries of 𝒆 are real linear forms in logarithms of algebraic numbers. But this is the form of an instance of ALIP. □

We are left with the task of showing that ALIP is decidable. The key tools here are Theorem 2.9 and Proposition 2.12. Proposition 4.3. ALIP is decidable.

Proof. We are given a convex polytope P = {𝒙 ∈ R 𝑑 : 𝜋𝐴𝒙 ≤ 𝒃}, where the entries of 𝐴 are real algebraic and the entries of 𝒃 are real linear forms in logarithms of algebraic numbers. We wish to decide whether P contains an integer point.

First we show how to reduce the problem of deciding whether P contains an integer point to finitely many instances of the problem of finding an integer point in a convex polytope Q of the form

Q = {𝒙 ∈ R 𝑑 : 𝐶𝒙 = 𝒅, 𝜋𝐸𝒙 < 𝒇 } , (14)
where the entries of 𝐶, 𝐸, 𝒅 are real algebraic and the entries of 𝒇 are real linear forms in logarithms of algebraic numbers. We will obtain a collection of such polytopes Q from P by replacing the non-strict inequality "≤" in every constraint of P with either strict inequality "<" or equality "=". To this end, note that when 𝒙 ∈ Z 𝑑 , 𝐴𝒙 is a vector with algebraic coefficients; so whenever 𝑏 𝑖 /𝜋 is transcendental (which can be effectively checked by Proposition 2.8) we may replace the inequality 𝜋 (𝐴𝒙) 𝑖 ≤ 𝑏 𝑖 in the definition of P with a strict inequality 𝜋 (𝐴𝒙) 𝑖 < 𝑏 𝑖 without affecting P ∩ Z 𝑑 . On the other hand, whenever 𝑏 𝑖 /𝜋 is algebraic, we split our problem into two cases: in the first case we replace the inequality 𝜋 (𝐴𝒙) 𝑖 ≤ 𝑏 𝑖 with an equality 𝜋 (𝐴𝒙) 𝑖 = 𝑏 𝑖 and in the second case we replace the inequality 𝜋 (𝐴𝒙) 𝑖 ≤ 𝑏 𝑖 with the strict inequality 𝜋 (𝐴𝒙) 𝑖 < 𝑏 𝑖 . Thus we obtain a finite collection of polytopes of the form [START_REF] Hall | Lie Groups, Lie Algebras, and Representations[END_REF].

Next we eliminate the equality constraints in the definition of Q so that only strict inequality constraints remain. Indeed by Proposition 2.6 we can compute an integer matrix 𝑀 and vector 𝒙 0 such that {𝒙 ∈ Z 𝑑 : 𝐶𝒙 = 𝒅} = {𝒙 0 + 𝑀𝒚 : 𝒚 ∈ Z 𝑑 ′ } for some 𝑑 ′ < 𝑑. Then the polytope Q ′ := {𝒚 ∈ R 𝑑 ′ : 𝜋𝐸 (𝒙 0 + 𝑀𝒚) < 𝒇 } contains an integer point iff Q contains an integer point. Now determining the existence of an integer point in a polytope of the form Q ′ is simply a version of ALIP in which all inequality constraints are strict.

It remains to show how to decide whether a polytope P := {𝒙 ∈ R 𝑑 : 𝜋𝐴𝒙 < 𝒃}, defined using only strict constraints, contains an integer point. To do this we first use Theorem 2.12 to decide whether P is non-empty. In case P is non-empty we can use Fourier-Motzkin elimination to find a vector 𝒒 ∈ Q 𝑑 and 𝜀 > 0 such that the closed 𝑙 1 -ball B with centre 𝒒 and radius 𝜀 with respect to the 𝑙 1 norm is contained in P.

The next step is to consider the Minkowski-Weyl decomposition of P, namely P = H + C, where H is the convex hull of finitely many points of P and C = {𝒙 ∈ R 𝑑 : 𝐴𝒙 ≤ 0} is a cone with an algebraic description. Note that P is bounded if and only if C = {0}, in which case the problem at hand is simple: consider the polytope Q with an algebraic description obtained by rounding up each coordinate of 𝒃/𝜋, which has the same conic part as P and which contains P, and therefore is bounded; finally, compute a bound on Q (such a bound can be defined in the first-order theory of the reals), which is also a bound on P, and test the integer points within that bound for membership in P. Otherwise,

C = {𝛼 1 𝒄 1 + • • • + 𝛼 𝑘 𝒄 𝑘 : 𝛼 1 , . . . , 𝛼 𝑘 ≥ 0},
where 𝒄 1 , . . . , 𝒄 𝑘 ∈ Q 𝑑 are the extremal rays of C. Note that 𝒒 + C ⊆ P and that B + C ⊆ P.

Now we consider a variation of an argument which appears in [START_REF] Khachiyan | Integer optimization on convex semialgebraic sets[END_REF]. Consider the computable set

L = C ⊥ ∩ Z 𝑑 .
If L = {0} then due to Theorem 2.9 it must be the case that there exist non-negative reals 𝜆 1 , . . . , 𝜆 𝑘 such that dist 𝒒 + 𝑘 ∑ 𝑖=1 𝜆 𝑖 𝒄 𝑖 , Z 𝑑 ≤ 𝜀, and we know that P ∩ Z 𝑑 ≠ ∅ from the fact that the closed ball B of centre 𝒒 and radius 𝜀 with respect to the 𝑙 1 norm is contained in P.

On the other hand, if L ≠ {0}, let 𝒛 ∈ L \ {0}. Since H is a bounded subset of R 𝑛 , the set

{𝒛 𝑇 𝒙 : 𝒙 ∈ P} = {𝒛 𝑇 𝒙 : 𝒙 ∈ H }

UNDECIDABILITY OF THE NON-COMMUTATIVE CASE

In this section we show that the Matrix Exponential Equation Problem and the Matrix-Exponential Semigroup Membership Problem are both undecidable in general.

Matrix-Exponential Equation Problem with Constraints

The proof of undecidability of MEP in the non-commutative case is by reduction from Hilbert's Tenth Problem. The reduction proceeds via several intermediate problems. These problems are obtained by augmenting MEP with various classes of arithmetic constraints on the real variables that appear in the statement of the problem. Definition 5.1. We consider the following three classes of arithmetic constraints over real variables 𝑡 1 , 𝑡 2 , . . .:

• E 𝜋 Z comprises constraints of the form 𝑡 𝑖 ∈ 𝛼 + 𝛽𝜋Z, where 𝛼 and 𝛽 ≠ 0 are real-valued constants such that cos(2𝛼𝛽 -1 ), 𝛽 are both algebraic numbers. • E + comprises linear equations of the form 𝛼 1 𝑡 1 + • • • + 𝛼 𝑛 𝑡 𝑛 = 𝛼 0 , for 𝛼 0 , . . . , 𝛼 𝑛 real algebraic constants. • E × comprises equations of the form 𝑡 ℓ = 𝑡 𝑖 𝑡 𝑗 . These constraints will be useful in defining polynomial relations, as well as in enforcing that certain variables be integer multiples of 𝜋. They will play a crucial role in the reduction from Hilbert's Tenth Problem.

A class of constraints E ⊆ E 𝜋 Z ∪ E + ∪ E × induces a generalisation of the MEP problem as follows:

Definition 5.2 (MEP with Constraints). Given a class of constraints E ⊆ E 𝜋 Z ∪ E + ∪ E × , the problem MEP(E) is as follows. An instance consists of real algebraic matrices 𝐴 1 , . . . , 𝐴 𝑘 , 𝐶 and a finite set of constraints 𝐸 ⊆ E on real variables 𝑡 1 , . . . , 𝑡 𝑘 . The question is whether there exist non-negative real values for 𝑡 1 , . . . , 𝑡 𝑘 such that 𝑘 𝑖=1 𝑒 𝐴 𝑖 𝑡 𝑖 = 𝐶 and the constraints 𝐸 are all satisfied.

Note that in the above definition of MEP(E) the set of constraints 𝐸 only utilises real variables 𝑡 1 , . . . , 𝑡 𝑘 appearing in the matrix equation 𝑘 𝑖=1 𝑒 𝐴 𝑖 𝑡 𝑖 = 𝐶. However, without loss of generality, we can allow constraints to utilise fresh variables 𝑡 𝑖 , for 𝑖 > 𝑘, since we can always define a corresponding matrix 𝐴 𝑖 = 0 for such variables for then 𝑒 𝐴 𝑖 𝑡 𝑖 = 𝐼 has no effect on the matrix product. In other words, we can without loss of generality have constraints in E with existentially quantified variables. In particular, we have the following useful observations:

• We can express inequality constraints of the form 𝑡 𝑖 ≠ 𝛼 in E + ∪ E × by using fresh variables 𝑡 𝑗 , 𝑡 ℓ . Indeed 𝑡 𝑖 ≠ 𝛼 is satisfied whenever there exist values of 𝑡 𝑗 and 𝑡 ℓ such that 𝑡 𝑖 = 𝑡 𝑗 + 𝛼 and 𝑡 𝑗 𝑡 ℓ = 1. • By using fresh variables, E + ∪E × can express polynomial constraints of the form 𝑃 (𝑡 1 , . . . , 𝑡 𝑛 ) = 𝑡 for 𝑃 a polynomial with integer coefficients. We illustrate the above two observations in an example.

Example 5.3. Consider the problem, given matrices 𝐴 1 , 𝐴 2 and 𝐶, to decide whether there exist We will make heavy use of the following proposition to combine several instances of the constrained MEP into a single instance by combining matrices block-wise. Proposition 5.4. Given real algebraic matrices 𝐴 1 , . . . , 𝐴 𝑘 , 𝐶 and 𝐴 ′ 1 , . . . , 𝐴 ′ 𝑘 , 𝐶 ′ , there exist real algebraic matrices 𝐴 ′′ 1 , . . . , 𝐴 ′′ 𝑘 , 𝐶 ′′ such that for all 𝑡 1 , . . . , 𝑡 𝑘 :

𝑡 1 , 𝑡 2 ≥ 0 such that 𝑒 𝐴 1 𝑡 1 𝑒 𝐴 2 𝑡 2 = 𝐶 and 𝑡 2 1 -1 = 𝑡 2 , 𝑡 2 ≠ 0 . This is equivalent
𝑘 𝑖=1 𝑒 𝐴 ′′ 𝑖 𝑡 𝑖 = 𝐶 ′′ ⇔ 𝑘 𝑖=1 𝑒 𝐴 𝑖 𝑡 𝑖 = 𝐶 ∧ 𝑘 𝑖=1 𝑒 𝐴 ′ 𝑖 𝑡 𝑖 = 𝐶 ′ .
Proof. For any 𝑖 ∈ {1, . . . , 𝑘 }, define

𝐴 ′′ 𝑖 = 𝐴 𝑖 0 0 𝐴 ′ 𝑖 , 𝐶 ′′ = 𝐶 0 0 𝐶 ′ .
The result follows because the matrix exponential can be computed block-wise (as is clear from its power series definition):

𝑘 𝑖=1 𝑒 𝐴 ′′ 𝑖 𝑡 𝑖 = 𝑘 𝑖=1 𝑒 𝐴 𝑖 𝑡 𝑖 0 0 𝑒 𝐴 ′ 𝑖 𝑡 𝑖 = 𝑘 𝑖=1 𝑒 𝐴 𝑖 𝑡 𝑖 0 0 𝑘 𝑖=1 𝑒 𝐴 ′ 𝑖 𝑡 𝑖 .

□

We remark that in the statement of Proposition 5.4 the two matrix equations that are combined are over the same set of variables. However, we can clearly combine any two matrix equations for which the common variables appear in the same order in the respective products.

The core of the reduction is to show that the constraints in E 𝜋 Z , E + and E × do not make the MEP problem harder. Proposition 5.5. MEP(E 𝜋 Z ∪ E + ∪ E × ) reduces to MEP(E + ∪ E × ).

Proof. Let 𝐴 1 , . . . , 𝐴 𝑘 , 𝐶 be real algebraic matrices and 𝐸 ⊆ E 𝜋 Z ∪ E + ∪ E × a finite set of constraints on real variables 𝑡 1 , . . . , 𝑡 𝑘 . Since 𝐸 is finite it suffices to show how to eliminate a single constraint in E 𝜋 Z ∩ 𝐸 from 𝐸.

Let 𝑡 𝑗 ∈ 𝛼 + 𝛽𝜋Z be a constraint in 𝐸. By definition of E 𝜋 Z we have that 𝛽 ≠ 0 and that both 𝛽 and cos(2𝛼𝛽 -1 ) are real algebraic. The Pythagorean theorem implies that sin(2𝛼𝛽 -1 ) is also real algebraic. Now define the following extra matrices:

𝐴 ′ 𝑗 = 0 2𝛽 -1 -2𝛽 -1 0 , 𝐶 ′ = cos(2𝛼𝛽 -1 ) sin(2𝛼𝛽 -1 )
sin(2𝛼𝛽 -1 ) cos(2𝛼𝛽 -1 ) .

Our assumptions ensure that 𝐴 ′ 𝑗 and 𝐶 ′ are both real algebraic. We now have the following chain of equivalences:

𝑒 𝐴 ′ 𝑗 𝑡 𝑗 = 𝐶 ′ ⇔ cos(2𝑡 𝑗 𝛽 -1 ) sin(2𝑡 𝑗 𝛽 -1 ) -sin(2𝑡 𝑗 𝛽 -1 ) cos(2𝑡 𝑗 𝛽 -1 ) = 𝐶 ′ ⇔ cos(2𝑡 𝑗 𝛽 -1 ) = cos(2𝛼𝛽 -1 ) ∧ sin(2𝑡 𝑗 𝛽 -1 ) = sin(2𝛼𝛽 -1 ) ⇔ 2𝛽 -1 𝑡 𝑗 ≡ 2𝛼𝛽 -1 (mod 2𝜋) ⇔ 𝑡 𝑗 ∈ 𝛼 + 𝛽𝜋Z.
Thus the additional matrix equation 𝑒 𝐴 ′ 𝑗 𝑡 𝑗 = 𝐶 ′ is equivalent to the constraint 𝑡 𝑗 ∈ 𝛼 +𝛽𝜋Z. Applying Proposition 5.4 we can thus eliminate this constraint. □ Proposition 5.6. MEP(E + ∪ E × ) reduces to MEP(E + ).

Proof. Let 𝐴 1 , . . . , 𝐴 𝑘 , 𝐶 be real algebraic matrices and 𝐸 ⊆ E + ∪ E × a finite set of constraints on variables 𝑡 1 , . . . , 𝑡 𝑘 . We proceed as above, showing how to remove each constraint in E × from 𝐸. In so doing we potentially increase the number and the dimension of matrices and add new constraints from E + .

Let 𝑡 𝑙 = 𝑡 𝑖 𝑡 𝑗 be an equation in 𝐸. To eliminate this equation the first step is to introduce fresh variables 𝑥, 𝑥 ′ , 𝑦, 𝑦 ′ , 𝑧 and add the constraints

𝑡 𝑖 = 𝑥, 𝑡 𝑗 = 𝑦, 𝑡 ℓ = 𝑧,
which are all in E + . We now add a new matrix equation over the fresh variables 𝑥, 𝑥 ′ , 𝑦, 𝑦 ′ , 𝑧 that is equivalent to the constraint 𝑥𝑦 = 𝑧. Since this matrix equation involves a new set of variables we are free to the set the order of the matrix products, which is crucial to express the desired constraint.

The key gadget is the following matrix product equation, which holds for any 𝑥, 𝑥 ′ , 𝑦, 𝑦 ′ , 𝑧 ⩾ 0:

      1 0 -𝑧 0 1 0 0 0 1             1 0 0 0 1 -𝑦 ′ 0 0 1             1 𝑥 0 0 1 0 0 0 1             1 0 0 0 1 𝑦 0 0 1             1 -𝑥 ′ 0 0 1 0 0 0 1       =       1 𝑥 -𝑥 ′ 𝑧 -𝑥𝑦 0 1 𝑦 -𝑦 ′ 0 0 1       .
Notice that each of the matrices on the left-hand side of the above equation has a single non-zero off-diagonal entry. Crucially each matrix of this form can be expressed as an exponential. Indeed we can write the above equation as a matrix-exponential product

𝑒 𝐵 1 𝑧 𝑒 𝐵 2 𝑦 ′ 𝑒 𝐵 3 𝑥 𝑒 𝐵 4 𝑦 𝑒 𝐵 5 𝑥 ′ =       1 𝑥 -𝑥 ′ 𝑧 -𝑥𝑦 0 1 𝑦 -𝑦 ′ 0 0 1       for matrices 𝐵 1 =       0 0 -1 0 0 0 0 0 0       𝐵 3 =       0 1 0 0 0 0 0 0 0       𝐵 5 =       0 -1 0 0 0 0 0 0 0       𝐵 2 =       0 0 0 0 0 -1 0 0 0       𝐵 4 =       0 0 0 0 0 1 0 0 0      
Thus the constraint 𝑥𝑦 = 𝑧 can be expressed as

𝑒 𝐵 1 𝑧 𝑒 𝐵 2 𝑦 ′ 𝑒 𝐵 3 𝑥 𝑒 𝐵 4 𝑦 𝑒 𝐵 5 𝑥 ′ = 𝐼 . (15)
Again, we can apply Proposition 5.4 to combine the equation ( 15) with the matrix equation from the original problem instance and thus encode the constraint 𝑧 = 𝑥𝑦. □ Proposition 5.7. MEP(E + ) reduces to MEP.

Proof. Let 𝐴 1 , . . . , 𝐴 𝑘 , 𝐶 be real algebraic matrices and 𝐸 ⊆ E + a set of constraints. We proceed as above, showing how to eliminate each constraint from 𝐸 that lies in E + , while preserving the set of solutions of the instance.

Let 𝛽 + 𝑘 𝑖=1 𝛼 𝑖 𝑡 𝑖 = 0 be an equation in 𝐸. Recall that 𝛽, 𝛼 1 , . . . , 𝛼 𝑘 are real algebraic. Define the extra matrices 𝐴 ′ 1 , . . . , 𝐴 ′ 𝑘 and 𝐶 ′ as follows:

𝐴 ′ 𝑖 = 0 𝛼 𝑖 0 0 , 𝐶 ′ = 1 -𝛽 0 1
.

Our assumptions ensure that 𝐴 ′ 1 , . . . , 𝐴 ′ 𝑘 and 𝐶 ′ are all real algebraic. Furthermore, the following extra product equation becomes:

𝑘 𝑖=1 𝑒 𝐴 ′ 𝑖 𝑡 𝑖 = 𝐶 ⇔ 𝑘 𝑖=1 1 𝛼 𝑖 𝑡 𝑖 0 1 = 1 -𝛽 0 1 ⇔ 𝑘 ∑ 𝑖=1 𝛼 𝑖 𝑡 𝑖 = -𝛽 .
The result follows by applying Proposition 5. On the decidability of membership in matrix-exponential semigroups :17

Reduction from Hilbert's Tenth Problem

Theorem 5.9. MEP is undecidable in the non-commutative case.

Proof. We have seen in the previous section that the problem MEP(E 𝜋 Z ∪ E + ∪ E × ) reduces to MEP without constraints. Thus it suffices to reduce Hilbert's Tenth Problem to MEP(E 𝜋 Z ∪ E + ∪ E × ). In fact the matrix equation will not play a role in the target of this reduction, only the additional constraints!

Let 𝑃 be a polynomial of total degree 𝑑 in 𝑘 variables with integer coefficients. From 𝑃 we build a homogeneous polynomial 𝑄, by adding a new variable 𝜆:

𝑄 (x, 𝜆) = 𝜆 𝑑 𝑃 𝑥 1 𝜆 , . . . , 𝑥 𝑘 𝜆 .
Note that 𝑄 still has integer coefficients. Furthermore, we have the relationship 𝑄 (x, 1) = 𝑃 (x).

As we have seen previously, it is easy to encode 𝑄 with constraints, in the sense that we can compute a finite set of constraints 𝐸 𝑄 ⊆ E + ∪E × utilising variables 𝑡 0 , . . . , 𝑡 𝑚 , 𝜆 such that 𝐸 is satisfied if and only if 𝑡 0 = 𝑄 (𝑡 1 , . . . , 𝑡 𝑘 , 𝜆). Note that 𝐸 𝑄 may need to utilise variables other than 𝑡 1 , . . . , 𝑡 𝑘 to do that. Another finite set of equations 𝐸 𝜋 Z ⊆ E 𝜋 Z is used to encode that 𝑡 1 , . . . , 𝑡 𝑘 , 𝜆 ∈ 𝜋Z. Finally, 𝐸 = ⊆ E + ∪ E × is used to encode 𝑡 0 = 0 and 1 ⩽ 𝜆 ⩽ 4. The latter is done by adding the polynomial equations 𝜆 = 1 + 𝛼 2 and 𝜆 = 4 -𝛽 2 for some 𝛼 and 𝛽. Finally we have the following chain of equivalences: ∃𝑡 0 , . . . , 𝜆 ⩾ 0 s. In this section, we will present a gadget matrix-exponential semigroup that can enforce a certain partial order on the matrices reaching a particular target. This will be useful to establish the reduction MEP ≤ MSMP. More precisely, we will exhibit five matrices 𝑊 , 𝑋, 𝑌 , 𝑍 and 𝐺 such that any product 𝐺 = 𝑝 𝑖=1 𝑒 𝐴 𝑖 𝑡 𝑖 where 𝑡 𝑖 > 0 and 𝐴 𝑖 ∈ {𝑊 , 𝑋, 𝑌 , 𝑍 } is such that all the "𝑋 " appear before the "𝑌 ". Define the following matrices:

𝑊 =       0 0 0 0 1 0 0 0 2       , 𝑋 =       0 0 0 0 0 1 0 0 0       , 𝑍 =       0 0 0 0 -1 0 0 0 -2       , 𝑌 =       0 1 0 0 0 0 0 0 0       , 𝐺 =       1 1 0 0 1 1 0 0 1       .
One easily computes the exponentials 𝑊 , 𝑋, 𝑌 , 𝑍 :

𝑒 𝑊 𝑡 =       1 0 0 0 𝑒 𝑡 0 0 0 𝑒 2𝑡       , 𝑒 𝑋𝑡 =       1 0 0 0 1 𝑡 0 0 1       , 𝑒 𝑌 𝑡 =       1 𝑡 0 0 1 0 0 0 1       , 𝑒 𝑍𝑡 =       1 0 0 0 𝑒 -𝑡 0 0 0 𝑒 -2𝑡       .
The crux of the proof will be based on the following asymmetry between 𝑋 and 𝑌 , which leaves the top right corner zero in one case but nonzero in the other. As we will later observe, once the top right corner is nonzero, it cannot be cleared.

𝑒 𝑋𝑡 𝑒 𝑌𝑢 =       1 𝑢 0 0 1 𝑡 0 0 1       , 𝑒 𝑌 𝑡 𝑒 𝑋𝑢 =       1 𝑢 𝑡𝑢 0 1 𝑡 0 0 1       .
Proposition 5.10. If there exist 𝑝 ∈ N, 𝐴 𝑖 ∈ {𝑊 , 𝑋, 𝑌 , 𝑍 } and 𝑡 𝑖 > 0, for 𝑖 ∈ {1, . . . , 𝑝}, such that 𝑝 𝑖=1 𝑒 𝐴 𝑖 𝑡 𝑖 = 𝐺, then the product contains at least one1 "𝑋 " and one "𝑌 ", and all the "𝑋 " appear before the "𝑌 ". Formally, there exist 𝑖 and 𝑗 such that 𝐴 𝑖 = 𝑋 and 𝐴 𝑗 = 𝑌 , and for any such choice we have 𝑖 < 𝑗.

Proof. First observe that any such product is always an upper triangular matrix with nonnegative entries (because all the matrices have non-negative entries) and positive entries on the diagonal. Let 𝑀 be such a matrix; we denote its coefficients by 0 if they are zero and + if they are positive. The following automaton should be read as follows: an arrow from 𝑀 to 𝑀 ′ annotated with 𝐴 means that any product of a matrix of the shape of 𝑀 by 𝑒 𝐴𝑡 with 𝑡 > 0 will give a matrix with the shape of 𝑀 ′ . Note that the empty product gives the identity. One easily checks that the following transitions hold. Starting from the identity and applying the different products 𝑒 𝐴 𝑖 𝑡 𝑖 in the automaton, it is clear that the only way to reach a matrix of the shape of 𝐺 is to have all the "𝑋 " before "𝑌 ". Formally, by contradiction, if there were 𝑖 < 𝑗 such that 𝐴 𝑖 = 𝑌 and 𝐴 𝑗 = 𝑋 then by the automaton, we would end up with a matrix where the top right corner is nonzero, which contradicts 𝐺 = 𝑝 𝑖=1 𝑒 𝐴 𝑖 𝑡 𝑖 . □ The previous lemma shows that this semigroup enforces a partial order on the matrices in products that reach the matrix 𝐺. The next lemma shows that 𝐺 can indeed be reached using this kind of products, essentially proving that 𝐺 belongs to this semigroup.

      + 0 0 0 + 0 0 0 +             + 0 0 0 + + 0 0 +             + + 0 0 + + 0 0 +             + + 0 0 + 0 0 0 +             + + + 0 + + 0 0 +      
On the decidability of membership in matrix-exponential semigroups :19 Proposition 5.11. For any positive real 𝑡, there exists a non-negative real 𝑢 such that 𝑒 𝑊 𝑢 𝑒 𝑋𝑡 𝑒 𝑌 𝑡 𝑒 𝑍𝑢 = 𝐺 or 𝑒 𝑍𝑢 𝑒 𝑋𝑡 𝑒 𝑌 𝑡 𝑒 𝑊 𝑢 = 𝐺 .

Proof. Consider the following products for an arbitrary 𝑢 ⩾ 0:

𝑒 𝑊 𝑢 𝑒 𝑋𝑡 𝑒 𝑌 𝑡 𝑒 𝑍𝑢 =       1 0 0 0 𝑒 𝑢 0 0 0 𝑒 2𝑢             1 𝑡 0 0 1 𝑡 0 0 1             1 0 0 0 𝑒 -𝑢 0 0 0 𝑒 -2𝑢       =       1 0 0 0 𝑒 𝑢 0 0 0 𝑒 2𝑢             1 𝑡𝑒 -𝑢 0 0 𝑒 -𝑢 𝑡𝑒 -2𝑢 0 0 𝑒 -2𝑢       =       1 𝑡𝑒 -𝑢 0 0 1 𝑡𝑒 -𝑢 0 0 1       , and
𝑒 𝑍𝑢 𝑒 𝑋𝑡 𝑒 𝑌 𝑡 𝑒 𝑊 𝑢 =       1 𝑡𝑒 𝑢 0 0 1 𝑡𝑒 𝑢 0 0 1       .
If 𝑡 ⩾ 1 then choosing 𝑢 = ln 𝑡 ⩾ 0 in the first product gives 𝐺, otherwise choosing 𝑢 = ln 1 𝑡 ⩾ 0 in the second product gives 𝐺. □

Undecidability of the Semigroup Membership Problem

We will now show the undecidability of MSMP.

In short, the difference is that we do not fix the order of the matrices in the product, and that each matrix may be used more than once. We will now show the following key result. Theorem 5.12. MSMP is undecidable in the non-commutative case.

Proof. We have seen in the previous section that MEP is undecidable in the non-commutative case. Thus it suffices to reduce MEP to MSMP to show undecidability.

Let 𝐴 1 , . . . , 𝐴 𝑘 , 𝐶 ∈ Q 𝑛×𝑛 be an instance of MEP. Denote by 𝐼 𝑚 the identity of size 𝑚, 0 𝑚 the zero matrix of size 𝑚. Recall the 3 × 3 matrices 𝑊 , 𝑋, 𝑌 , 𝑍, 𝐺, defined in Section 5.3. For every 𝑖 ∈ {2, . . . , 𝑘 -1}, define the following matrices:

𝐵 𝑖 =           𝐴 𝑖 0 3(𝑖-2) 𝑌 𝑋 0 3(𝑘-1-𝑖)           , 𝐵 ′ 𝑖 =           0 𝑛 0 3(𝑖-2) 𝑌 𝑋 0 3(𝑘-1-𝑖)           .
We also define the matrices

𝐵 1 =       𝐴 1 𝑋 0 3(𝑘-2)       , 𝐵 ′ 1 =       0 𝑛 𝑋 0 3(𝑘-2)       , 𝐵 𝑘 =       𝐴 1 0 3(𝑘-2) 𝑌       , 𝐵 ′ 𝑘 =       0 𝑛 0 3(𝑘-2) 𝑌      
, and, for 𝑖 ∈ {1, . . . , 𝑘 -1},

𝑊 𝑖 =         0 𝑛 0 3(𝑖-1) 𝑊 0 3(𝑘-1-𝑖)         , 𝑍 𝑖 =         0 𝑛 0 3(𝑖-1) 𝑍 0 3(𝑘-1-𝑖)        
.

Finally, we define the target matrix:

𝐶 ′ =          𝐶 𝐺 . . . 𝐺         
.

We can now define our MSMP instance as follows, the target matrix is 𝐶 ′ and the semigroup G is generated by

𝑒 𝐵 𝑖 𝑡 𝑖 , 𝑒 𝐵 ′ 𝑖 𝑡 𝑖 : 𝑡 𝑖 ⩾ 0, 𝑖 = 1, . . . , 𝑘 ∪ 𝑒 𝑊 𝑖 𝑡 𝑖 , 𝑒 𝑍 𝑖 𝑡 𝑖 : 𝑡 𝑖 ⩾ 0, 𝑖 = 1, . . . , 𝑘 -1 .
We claim the original instance of MEP is satisfiable if and only if 𝐶 ′ ∈ G. Let us examine both directions independently. Assume that the MEP instance is satisfiable. Then there exist 𝑡 1 , . . . , 𝑡 𝑘 ⩾ 0 such that:

𝑘 𝑖=1 𝑒 𝐴 𝑖 𝑡 𝑖 = 𝐶.
Define 𝜏 = max{𝑡 1 , . . . , 𝑡 𝑘 } + 1 (note that 𝜏 > 0) and 𝑡 ′ 𝑖 = 𝜏 -𝑡 𝑖 ⩾ 0 for every 𝑖 ∈ {1, . . . , 𝑘 }. A straightforward calculation shows that:

𝑘 𝑖=1 𝑒 𝐵 𝑖 𝑡 𝑖 𝑒 𝐵 ′ 𝑖 𝑡 ′ 𝑖 =          𝑘 𝑖=1 𝑒 𝐴 𝑖 𝑡 𝑖 𝑒 𝑋𝜏 𝑒 𝑌𝜏 . . . 𝑒 𝑋𝜏 𝑒 𝑌𝜏          =          𝐶 𝑈 . . . 𝑈         
, where 𝑈 = 𝑒 𝑋𝜏 𝑒 𝑌𝜏 . Apply Proposition 5.11 to get 𝜆 ⩾ 0 such that either 𝑒 𝑊 𝜆 𝑈 𝑒 𝑍 𝜆 = 𝐺 or 𝑒 𝑍 𝜆 𝑈 𝑒 𝑊 𝜆 = 𝐺. In the first case, conclude by checking that

𝑘-1 𝑖=1 𝑒 𝑊 𝑖 𝜆 𝑘 𝑖=1 𝑒 𝐵 𝑖 𝑡 𝑖 𝑒 𝐵 ′ 𝑖 𝑡 ′ 𝑖 𝑘-1 𝑖=1 𝑒 𝑍 𝑖 𝜆 =          𝐶 𝐺 . . . 𝐺          = 𝐶 ′ .
In the second case, exchange the 𝑊 𝑖 and 𝑍 𝑖 to get same result. This concludes the proof that the MSMP instance is satisfiable, since all the products belong to G.

Assume the MSMP instance is satisfiable. Then there exist 𝑡 1 , . . . , 𝑡 𝑚 > 0 (we can always take them positive) and 𝑀 1 , . . . , 𝑀 𝑚 ∈ 𝐵 𝑖 , 𝐵 ′ 𝑖 : 𝑖 = 1, . . . , 𝑘 } ∪ 𝑊 𝑖 , 𝑍 𝑖 : 𝑖 = 1, . . . , 𝑘 -1 such that

𝑚 𝑗=1 𝑒 𝑀 𝑗 𝑡 𝑗 = 𝐶 ′ . (16)
Observe that by construction, this product has the following form:

𝑚 𝑗=1 𝑒 𝑀 𝑗 𝑡 𝑗 =          𝑉 𝑈 1 . . . 𝑈 𝑘-1         
, where 𝑉 belongs to the semigroup generated by {𝑒 𝐴 𝑖 𝑡 : 𝑡 ⩾ 0} and 𝑈 𝑖 belongs to the semigroup generated by {𝑒 𝑊 𝑡 , 𝑒 𝑋𝑡 , 𝑒 𝑌 𝑡 , 𝑒 𝑍𝑡 : 𝑡 ⩾ 0}. Since [START_REF] Henzinger | What's decidable about hybrid automata?[END_REF] implies that 𝑈 𝑖 = 𝐺, we can apply Proposition 5.10 to get each product producing 𝑈 𝑖 must have all its "𝑋 " before its "𝑌 ". Furthermore, each 𝑈 𝑖 must contain at least one 𝑋 and one 𝑌 in its product. For any 𝑖 ∈ {1, . . . , 𝑘 }, let 𝑘 𝑖 (resp., 𝑘 ′ 𝑖 ) denote the first (resp., last) index 𝑗 such that 𝑀 𝑗 = 𝐵 𝑖 or 𝐵 ′ 𝑖 . Those indices exist because of the proposition since at least one 𝐵 𝑖 or 𝐵 𝑖 ' must appear for every 𝑖 to get both an 𝑋 and a 𝑌 in each product giving 𝑈 𝑖 . Obviously 𝑘 𝑖 ⩽ 𝑘 ′ 𝑖 by definition. We now claim that the proposition implies that:

𝑘 1 ⩽ 𝑘 ′ 1 < 𝑘 2 ⩽ 𝑘 ′ 2 < 𝑘 3 • • • < 𝑘 𝑘-1 ⩽ 𝑘 ′ 𝑘-1 .
Indeed, Proposition 5.10 ensures that in the product giving 𝑈 1 , all the "𝑋 " appear before the "𝑌 ", but the only matrices that contribute some 𝑋 to 𝑈 1 are 𝐵 1 and 𝐵 ′ 1 , and the only matrices that contribute some 𝑌 to 𝑈 1 are 𝐵 2 and 𝐵 ′ 2 . Thus 𝑘 ′ 1 < 𝑘 2 , i.e. the last "𝑋 " coming from 𝐵 1 or 𝐵 ′ 1 is before the first "𝑌 " coming from 𝐵 2 or 𝐵 ′ 2 . A similar reasoning ensures that 𝑘 ′ 2 < 𝑘 3 and so on. This shows that for any 𝑖 ∈ {1, . . . , 𝑘 }, if 𝑀 𝑗 = 𝐵 𝑖 then 𝑗 ∈ {𝑘 𝑖 , . . . , 𝑘 ′ 𝑖 }. Thus all the 𝐵 1 appear before the 𝐵 2 which appear before the 𝐵 3 and so on. However, since the 𝐵 𝑖 are the only ones to contribute to 𝑉 , then 𝑉 must be of the form:

𝑉 = 𝑘 𝑖=1 𝑒 𝐴 𝑖 𝑡 ′ 𝑖 ,
where 𝑡 ′ 𝑖 ⩾ 0 is the sum of all 𝑡 𝑗 such that 𝑀 𝑗 = 𝐵 𝑖 . Finally 𝑉 = 𝐶, so the instance of MEP is satisfiable. □

VECTOR AND HYPERPLANE REACHABILITY

In this section we show that the vector and halfspace reachabililty problems for matrix-exponential semigroups, as given in Definition 1.4, are both undecidable.

Theorem 6.1. The Matrix-Exponential Vector Reachability Problem is undecidable.

Proof. This can be shown by reduction from the membership problem for matrix-exponential semigroups. In particular, given square matrices 𝐵 1 , . . . , 𝐵 𝑘 , 𝐶, we construct matrices 𝐴 1 , . . . , 𝐴 𝑘 and vectors 𝒙, 𝒚 for which

Let 𝒄 , . . . , 𝒄 𝑛 be the columns of 𝐶, from left to right, and let 𝒆 1 , . . . , 𝒆 𝑛 denote the canonical basis of R 𝑛 . Then [START_REF] Kannan | Polynomial-time algorithm for the orbit problem[END_REF] Proof. This can be shown by reduction from the vector reachability problem. Similarly to what we did in the previous proof, we will define matrices 𝐶 1 , . . . , 𝐶 𝑘 and vectors 𝒘, 𝒛 such that have shown that the Matrix-Exponential Semigroup Membership Problem is undecidable in general, but decidable when the generating matrices 𝐴 1 , . . . , 𝐴 𝑘 commute. Our results are analogous to what is known for the discrete version of this problem-the Matrix Semigroup Membership Problem-namely decidability in the commutative case and undecidability in general (see Section 1.1). Finally, we have shown that the Matrix-Exponential Semigroup Membership Problem is in Σ 1 if Schanuel's conjecture is true, and in Σ 2 unconditionally. Note that for the Matrix Semigroup Membership Problem, membership in Σ 1 follows trivially from the fact that a finitely generated matrix semigroup is recursively enumerable.

It would be interesting to look at possibly decidable restrictions of Matrix-Exponential Semigroup Membership Problem: for example, the case with two non-commuting generators, which was shown to be decidable in the case of the analogous discrete problem in [START_REF] Bell | Matrix equations and Hilbert's Tenth Problem[END_REF]. Bounding the dimension of the ambient vector space might also yield decidability, along the lines of results in the discrete case in [START_REF] Potapov | Decidability of the membership problem for 2 × 2 integer matrices[END_REF]. Finally, deriving upper and lower bounds for the computational complexity of the commutative case remains to be addressed.

□ 2 . 1 . 3 (- 1 )

 2131 Matrix Logarithms. Given a matrix 𝐴 ∈ C 𝑑×𝑑 , define the matrix logarithm log(𝐴) := ∞ ∑ 𝑚=1 𝑚+1 (𝐴 -𝐼 ) 𝑚 𝑚 ∈ C 𝑑×𝑑

Proposition 4 . 2 .

 42 LEP reduces to ALIP.Proof. Consider an instance of LEP, comprising a system of equations exp 𝑘 ℓ=1 𝜆 ( 𝑗) ℓ 𝑡 ℓ = 𝑐 𝑗 exp(𝑑 𝑗 ) 𝑗 ∈ {1, . . . , 𝑚},

Theorem 4 . 4 .

 44 is a bounded subset of R. Therefore there exist 𝑎, 𝑏 ∈ Z such that ∀𝒙 ∈ P, 𝑎 ≤ 𝒛 𝑇 𝒙 ≤ 𝑏, so we can reduce our problem to 𝑏 -𝑎 + 1 lower-dimensional instances by finding the integer points of {𝒙 ∈ P : 𝒛 𝑇 𝒙 = 𝑖}, for 𝑖 ∈ {𝑎, . . . , 𝑏}. Note that we have seen earlier in the proof how to reduce the dimension of the ambient space when the polytope P is contained in an affine hyperplane. □ Putting together Proposition 4.1, Proposition 4.2, and Proposition 4.3, we obtain: The Matrix-Exponential Semigroup Membership Problem (as given in Definition 1.1) is decidable in case the generating matrices 𝐴 1 , . . . , 𝐴 𝑘 commute.

5 𝑖=1𝑒

 5 to the following instance of MEP(E + ∪E × ): decide whether there exist 𝑡 1 , . . . , 𝑡 5 ≥ 0 such that 𝐴 𝑖 𝑡 𝑖 = 𝐶 and𝑡 1 𝑡 1 = 𝑡 3 , 𝑡 3 -1 = 𝑡 2 , 𝑡 2 𝑡 4 = 𝑡 5 , 𝑡 5 = 1where 𝐴 1 , 𝐴 2 and 𝐶 are as above and 𝐴 3 = 𝐴 4 = 𝐴 5 = 0.

  4. □ Combining Proposition 5.5, Proposition 5.6, and Proposition 5.7 we have: Proposition 5.8. MEP(E 𝜋 Z ∪ E + ∪ E × ) reduces to MEP.

  𝑚 𝑗=1 exp(𝐵 𝑖 𝑗 𝑡 𝑗 ) = 𝐶 ⇔ 𝑚 𝑗=1 exp(𝐴 𝑖 𝑗 𝑡 𝑗 )𝒙 = 𝒚.

𝐵

  𝑖 𝑡 𝑖 )𝒙 = 𝒚 ⇔ 𝒘 𝑇 𝑘 𝑖=1 exp(𝐶 𝑖 𝑡 𝑖 )𝒛 = 0 .Let 𝒆 1 , . . . , 𝒆 𝑛 denote the canonical basis of R 𝑛 . Moreover, let𝐵 𝑖 = 𝑖 ⊗ 𝐼 + 𝐼 ⊗ 𝐵 𝑖 • 𝐵 𝑖 ⊗ 𝐼 + 𝐼 ⊗ 𝐵 𝑖 . Then 𝑘 𝑖=1 exp(𝐴 𝑖 𝑡 𝑖 )𝒙 = 𝒚 ⇔ 𝐵 𝑖 𝑡 𝑖 ) ⊗ exp(𝐵 𝑖 𝑡 𝑖 )) (𝒗 ⊗ 𝒗) 𝑖 ⊗ 𝐼 + 𝐼 ⊗ 𝐵 𝑖 )𝑡 𝑖 ) (𝒗 ⊗ 𝒗) = 0 ⇔ 𝒖 1 ⊗ 𝒖 1 . . .𝒖 𝑛 ⊗ 𝒖 𝑛 𝑇 𝑘 𝑖=1 exp(𝐶 𝑖 𝑡 𝑖 ) 𝒗 ⊗ 𝒗 . . . 𝒗 ⊗ 𝒗 = 0.

  2.1.4 Properties of commuting matrices. We present a useful decomposition of C 𝑑 induced by the commuting matrices 𝐴 1 , . . . , 𝐴 𝑘 ∈ C 𝑑×𝑑 (cf. [8, Section 2]). Recall that 𝜎 (𝐴 𝑖 ) denotes the spectrum of the matrix 𝐴 𝑖 and fix 𝝀 = (𝜆 1 , . . . , 𝜆 𝑘 ) ∈ 𝜎 (𝐴 1 ) × • • • × 𝜎 (𝐴 𝑘 ). Note that the generalised eigenspace of 𝜆 𝑖 of 𝐴 𝑖 is equal to ker (𝐴 𝑖 -𝜆 𝑖 𝐼 ) 𝑑 . (This is because the increasing sequence (ker (𝐴 𝑖 -𝜆 𝑖 𝐼 ) 𝑛 ) 𝑛 ∈N of subspaces of C 𝑑 must converge in at most 𝑑 steps.) With this in mind, we define the following subspace of C 𝑑 :

  t. 𝐸 𝑄 ∪ 𝐸 𝜋 Z ∪ 𝐸 = is satisfied ⇔ ∃𝑡 1 , . . . , 𝜆 ⩾ 0 s.t. 0 = 𝑄 (𝑡 1 , . . . , 𝑡 𝑘 , 𝜆) ∧ 𝑡 1 , . . . , 𝑡 𝑘 , 𝜆 ∈ 𝜋Z ∧ 1 ⩽ 𝜆 ⩽ 4 ⇔ ∃𝑛 1 , . . . , 𝑛 𝑘 ∈ N s.t. 0 = 𝑄 (𝜋𝑛 1 , . . . , 𝜋𝑛 𝑘 , 𝜋) ⇔ ∃𝑛 1 , . . . , 𝑛 𝑘 ∈ N s.t. 0 = 𝜋 𝑑 𝑄 (𝑛 1 , . . . , 𝑛 𝑘 , 1) ⇔ ∃𝑛 1 , . . . , 𝑛 𝑘 ∈ N s.t. 0 = 𝑃 (𝑛 1 , . . . , 𝑛 𝑘 ).

	□
	5.3 Enforcing a Matrix Product Order

  can be achieved by setting, for each 𝑖 ∈ {1, . . . , 𝑛}, The Matrix-Exponential Hyperplane Reachability Problem is undecidable.

		𝐵 𝑖		• • •	0
	𝐴 𝑖 =	. . .		. . .	. . .	∈ R 𝑛 2 ×𝑛 2	,
		0		• • •	𝐵 𝑖
	as well as
			𝒆 1			𝒄 1
		𝒙 =	. . .	and 𝒚 =	. . .	.
			𝒆 𝑛			𝒄 𝑛
							□
	Theorem 6.2.

Journal of the ACM, Vol. 1, No. 1, Article . Publication date: December 2020.

Note that this is not entirely trivial because we required only positive 𝑡 𝑖 in the product. Journal of the ACM, Vol. 1, No. 1, Article . Publication date: December

* Supported by ERC grant AVS-ISS (648701), and by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) -Projektnummer 389792660 -TRR 248.

† Supported by EPSRC Fellowship EP/N008197/

The then follows by taking We are interested in classifying the Turing-degree of MSMP. Recall that the first level of the arithmetical hierarchy, denoted Σ 1 , consists of the recursively enumerable languages, while the second level of the arithmetical hierarchy, denoted Σ 2 , consists of the languages that can be enumerated by a Turing machine with an oracle to a language in Σ 1 .

Theorem 7.1. MSMP lies in Σ 2 .

Proof. Given an instance of MSMP, determined by generating matrices 𝐴 1 , . . . , 𝐴 𝑘 and target 𝐶, consider the functions 𝑓 𝒘 : R |𝒘 | → R, defined for each 𝒘 ∈ {1, . . . , 𝑘 } * by

where ∥ • ∥ 𝐹 denotes the Frobenius norm of a matrix (obtained as the positive square root of the sum of the squares of the matrix entries). Note that each 𝑓 𝒘 is an exponential-polynomial which takes values in the nonnegative reals. Clearly, the given instance of MSMP is positive if and only if some 𝑓 𝒘 has a (necessarily tangential) zero.

Before proceeding, note that exponential-polynomials are closed under differentiation, and that they are computable functions.

Let 𝒃 : N → {1, . . . , 𝑘 } * be any computable surjection. For each 𝑛 ∈ N and 𝒘 ∈ {𝒃 (1), . . . , 𝒃 (𝑛)}, consider the Turing machine 𝐴 𝒘,𝑛 that does the following: for each 𝑚 ∈ N, partition [0, 𝑛] |𝒘 | in a uniform grid, with mesh size 𝑚 -1 , and compute the approximate value of 𝑓 𝒘 with error at most 𝑚 -1 at each grid point; if it is ever the case that all the approximate values of 𝑓 𝒘 are greater than

𝑚 -1 (where 𝐿 𝒘,𝑛 is an upper bound on ∥∇𝑓 𝒘 ∥ ↾ [0,𝑛] , which we can compute by using the triangle inequality and the monotonicity of the exponential function), 𝐴 𝒘,𝑛 halts. Due to the Mean Value Theorem and to the compactness of [0, 𝑛], 𝐴 𝒘,𝑛 halts if and only if 𝑓 𝒘 ↾ [0,𝑛] does not have a zero. Thus, the instance of MSMP is positive if and only if some 𝐴 𝒘,𝑛 does not halt. Now, consider the Turing machine 𝐵 with access to an oracle for the Halting Problem that, for each 𝑛 ∈ N and 𝒘 ∈ {𝒃 (1), . . . , 𝒃 (𝑛)}, uses the oracle to decide whether 𝐴 𝒘,𝑛 halts and 𝐵 only if halts if some oracle call determines that 𝐴 𝒘,𝑛 runs forever. Then 𝐵 halts if and only if the MSMP instance in consideration is positive. □ Moreover, the following result holds.

Theorem 7.2. If Schanuel's conjecture is true then MSMP lies in Σ 1 .

Proof. Let 𝑓 𝒘 , 𝒘 ∈ {1, . . . , 𝑘 } ★ be as in the proof of Theorem 7.1. Consider the Turing Machine 𝑇 which, for each 𝑛 ∈ N and 𝒘 ∈ {𝒃 (1), . . . , 𝒃 (𝑛)}, uses Theorem 2.10 to decide whether 𝑓 𝒘 admits a zero in the region [0, 𝑛] |𝒘 | , and halts when such a zero is found. Then 𝑇 halts if and only if the instance of MSMP under consideration is positive. □