grandes-ecoles

Papers (191)
2025
centrale-maths1__official 40 centrale-maths2__official 42 mines-ponts-maths1__mp 20 mines-ponts-maths1__pc 21 mines-ponts-maths1__psi 21 mines-ponts-maths2__mp 28 mines-ponts-maths2__pc 24 mines-ponts-maths2__psi 26 polytechnique-maths-a__mp 27 polytechnique-maths__fui 16 polytechnique-maths__pc 27 x-ens-maths-a__mp 18 x-ens-maths-c__mp 9 x-ens-maths-d__mp 38 x-ens-maths__pc 27 x-ens-maths__psi 38
2024
centrale-maths1__official 28 centrale-maths2__official 29 geipi-polytech__maths 9 mines-ponts-maths1__mp 25 mines-ponts-maths1__pc 20 mines-ponts-maths1__psi 19 mines-ponts-maths2__mp 23 mines-ponts-maths2__pc 21 mines-ponts-maths2__psi 21 polytechnique-maths-a__mp 44 polytechnique-maths-b__mp 37 x-ens-maths-a__mp 43 x-ens-maths-b__mp 35 x-ens-maths-c__mp 22 x-ens-maths-d__mp 45 x-ens-maths__pc 24 x-ens-maths__psi 26
2023
centrale-maths1__official 44 centrale-maths2__official 33 e3a-polytech-maths__mp 4 mines-ponts-maths1__mp 15 mines-ponts-maths1__pc 23 mines-ponts-maths1__psi 23 mines-ponts-maths2__mp 22 mines-ponts-maths2__pc 18 mines-ponts-maths2__psi 22 polytechnique-maths__fui 23 x-ens-maths-a__mp 25 x-ens-maths-b__mp 24 x-ens-maths-c__mp 20 x-ens-maths-d__mp 20 x-ens-maths__pc 18 x-ens-maths__psi 15
2022
centrale-maths1__mp 48 centrale-maths1__official 48 centrale-maths1__pc 37 centrale-maths1__psi 43 centrale-maths2__mp 32 centrale-maths2__official 32 centrale-maths2__pc 39 centrale-maths2__psi 45 mines-ponts-maths1__mp 25 mines-ponts-maths1__pc 24 mines-ponts-maths1__psi 24 mines-ponts-maths2__mp 24 mines-ponts-maths2__pc 19 mines-ponts-maths2__psi 20 x-ens-maths-a__mp 13 x-ens-maths-b__mp 40 x-ens-maths-c__mp 27 x-ens-maths-d__mp 46 x-ens-maths1__mp 13 x-ens-maths2__mp 40 x-ens-maths__pc 15 x-ens-maths__pc_cpge 15 x-ens-maths__psi 22 x-ens-maths__psi_cpge 23
2021
centrale-maths1__mp 40 centrale-maths1__official 40 centrale-maths1__pc 36 centrale-maths1__psi 29 centrale-maths2__mp 30 centrale-maths2__official 29 centrale-maths2__pc 38 centrale-maths2__psi 37 x-ens-maths2__mp 39 x-ens-maths__pc 44
2020
centrale-maths1__mp 42 centrale-maths1__official 42 centrale-maths1__pc 36 centrale-maths1__psi 40 centrale-maths2__mp 38 centrale-maths2__official 38 centrale-maths2__pc 40 centrale-maths2__psi 39 mines-ponts-maths1__mp_cpge 24 mines-ponts-maths2__mp_cpge 21 x-ens-maths-a__mp_cpge 18 x-ens-maths-b__mp_cpge 20 x-ens-maths-d__mp 14 x-ens-maths1__mp 18 x-ens-maths2__mp 20 x-ens-maths__pc 18
2019
centrale-maths1__mp 37 centrale-maths1__official 37 centrale-maths1__pc 40 centrale-maths1__psi 39 centrale-maths2__mp 37 centrale-maths2__official 37 centrale-maths2__pc 39 centrale-maths2__psi 49 x-ens-maths1__mp 24 x-ens-maths__pc 18 x-ens-maths__psi 26
2018
centrale-maths1__mp 47 centrale-maths1__official 47 centrale-maths1__pc 41 centrale-maths1__psi 44 centrale-maths2__mp 44 centrale-maths2__official 44 centrale-maths2__pc 35 centrale-maths2__psi 38 x-ens-maths1__mp 19 x-ens-maths2__mp 17 x-ens-maths__pc 22 x-ens-maths__psi 24
2017
centrale-maths1__mp 45 centrale-maths1__official 45 centrale-maths1__pc 22 centrale-maths1__psi 17 centrale-maths2__mp 30 centrale-maths2__official 30 centrale-maths2__pc 28 centrale-maths2__psi 44 x-ens-maths1__mp 26 x-ens-maths2__mp 16 x-ens-maths__pc 18 x-ens-maths__psi 26
2016
centrale-maths1__mp 42 centrale-maths1__pc 31 centrale-maths1__psi 33 centrale-maths2__mp 25 centrale-maths2__pc 47 centrale-maths2__psi 27 x-ens-maths1__mp 18 x-ens-maths2__mp 46 x-ens-maths__pc 15 x-ens-maths__psi 20
2015
centrale-maths1__mp 42 centrale-maths1__pc 18 centrale-maths1__psi 42 centrale-maths2__mp 44 centrale-maths2__pc 18 centrale-maths2__psi 33 x-ens-maths1__mp 16 x-ens-maths2__mp 31 x-ens-maths__pc 30 x-ens-maths__psi 22
2014
centrale-maths1__mp 28 centrale-maths1__pc 26 centrale-maths1__psi 27 centrale-maths2__mp 24 centrale-maths2__pc 26 centrale-maths2__psi 27 x-ens-maths1__mp 9 x-ens-maths2__mp 16 x-ens-maths__pc 4 x-ens-maths__psi 24
2013
centrale-maths1__mp 22 centrale-maths1__pc 45 centrale-maths1__psi 29 centrale-maths2__mp 31 centrale-maths2__pc 52 centrale-maths2__psi 32 x-ens-maths1__mp 24 x-ens-maths2__mp 35 x-ens-maths__pc 22 x-ens-maths__psi 9
2012
centrale-maths1__mp 36 centrale-maths1__pc 28 centrale-maths1__psi 33 centrale-maths2__mp 27 centrale-maths2__psi 18
2011
centrale-maths1__mp 27 centrale-maths1__pc 17 centrale-maths1__psi 24 centrale-maths2__mp 29 centrale-maths2__pc 17 centrale-maths2__psi 10
2010
centrale-maths1__mp 19 centrale-maths1__pc 30 centrale-maths1__psi 13 centrale-maths2__mp 32 centrale-maths2__pc 37 centrale-maths2__psi 27
2025 x-ens-maths-d__mp

38 maths questions

Q1 Sequences and Series Properties and Manipulation of Power Series or Formal Series View
Show that the set of quasi-polynomial functions forms a $\mathbb{C}$-vector space.
Q2 Sequences and Series Properties and Manipulation of Power Series or Formal Series View
Show that if $P, Q : \mathbb{Z} \rightarrow \mathbb{C}$ are two quasi-polynomial functions such that $P(n) = Q(n)$ for all $n \geq 0$, then $P = Q$.
Q3 Sequences and Series Properties and Manipulation of Power Series or Formal Series View
Show that a function $P : \mathbb{Z} \rightarrow \mathbb{C}$ is quasi-polynomial if and only if there exist an integer $m \in \mathbb{N}^*$ and $m$ polynomials $P_0, \ldots, P_{m-1}$ with complex coefficients such that for all $j \in \{0, \ldots, m-1\}$ and for all $n \in \mathbb{Z}$ congruent to $j$ modulo $m$, we have $P(n) = P_j(n)$.
Q4 Sequences and Series Properties and Manipulation of Power Series or Formal Series View
Let $\omega$ be a root of unity and $p \in \mathbb{N}^*$. Let $\sum_{n=0}^{+\infty} R(n) x^n$ denote the power series expansion of $\frac{1}{(1 - \omega x)^p}$. Show that $R$ is a quasi-polynomial function then determine its degree and its leading coefficient.
Q5 Sequences and Series Power Series Expansion and Radius of Convergence View
Let $k \in \mathbb{N}^*$ and $(a_1, \ldots, a_k) \in (\mathbb{N}^*)^k$ a $k$-tuple of strictly positive integers. When $k \geq 2$, we assume they are coprime as a set. We define a function $P : \mathbb{N} \rightarrow \mathbb{C}$ by setting for all $n \in \mathbb{N}$: $$P(n) = \operatorname{Card}\left\{(n_1, \ldots, n_k) \in \mathbb{N}^k : n_1 a_1 + \cdots + n_k a_k = n\right\},$$ then we define the power series $F(x) = \sum_{n=0}^{\infty} P(n) x^n$.
Show that the radius of convergence of $F$ is greater than or equal to 1.
Q6 Sequences and Series Functional Equations and Identities via Series View
Let $k \in \mathbb{N}^*$ and $(a_1, \ldots, a_k) \in (\mathbb{N}^*)^k$ a $k$-tuple of strictly positive integers. When $k \geq 2$, we assume they are coprime as a set. We define a function $P : \mathbb{N} \rightarrow \mathbb{C}$ by setting for all $n \in \mathbb{N}$: $$P(n) = \operatorname{Card}\left\{(n_1, \ldots, n_k) \in \mathbb{N}^k : n_1 a_1 + \cdots + n_k a_k = n\right\},$$ then we define the power series $F(x) = \sum_{n=0}^{\infty} P(n) x^n$.
Prove the equality $F(x) = \prod_{i=1}^{k} \frac{1}{1 - x^{a_i}}$ for all $x \in ]-1, 1[$.
Q7 Sequences and Series Properties and Manipulation of Power Series or Formal Series View
Let $k \in \mathbb{N}^*$ and $(a_1, \ldots, a_k) \in (\mathbb{N}^*)^k$ a $k$-tuple of strictly positive integers. When $k \geq 2$, we assume they are coprime as a set. We define a function $P : \mathbb{N} \rightarrow \mathbb{C}$ by setting for all $n \in \mathbb{N}$: $$P(n) = \operatorname{Card}\left\{(n_1, \ldots, n_k) \in \mathbb{N}^k : n_1 a_1 + \cdots + n_k a_k = n\right\},$$ then we define the power series $F(x) = \sum_{n=0}^{\infty} P(n) x^n$.
Deduce that $P$ is a quasi-polynomial function.
Q8 Sequences and Series Properties and Manipulation of Power Series or Formal Series View
Let $k \in \mathbb{N}^*$ and $(a_1, \ldots, a_k) \in (\mathbb{N}^*)^k$ a $k$-tuple of strictly positive integers. When $k \geq 2$, we assume they are coprime as a set. We define a function $P : \mathbb{N} \rightarrow \mathbb{C}$ by setting for all $n \in \mathbb{N}$: $$P(n) = \operatorname{Card}\left\{(n_1, \ldots, n_k) \in \mathbb{N}^k : n_1 a_1 + \cdots + n_k a_k = n\right\},$$ then we define the power series $F(x) = \sum_{n=0}^{\infty} P(n) x^n$.
Calculate the leading coefficient of $P$.
Q9 Sequences and Series Recurrence Relations and Sequence Properties View
Let $k \in \mathbb{N}^*$ and $(a_1, \ldots, a_k) \in (\mathbb{N}^*)^k$ a $k$-tuple of strictly positive integers. When $k \geq 2$, we assume they are coprime as a set. We define a function $P : \mathbb{N} \rightarrow \mathbb{C}$ by setting for all $n \in \mathbb{N}$: $$P(n) = \operatorname{Card}\left\{(n_1, \ldots, n_k) \in \mathbb{N}^k : n_1 a_1 + \cdots + n_k a_k = n\right\}.$$ We assume $k = 2$. We assume in this question that $(a_1, a_2) = (2, 3)$. Construct a function $\phi : \mathbb{Z} \rightarrow \mathbb{Z}$ of period 6 such that $P(n) = \frac{n + \phi(n)}{6}$ for all $n \in \mathbb{N}$.
Q10 Partial Fractions View
Let $k \in \mathbb{N}^*$ and $(a_1, \ldots, a_k) \in (\mathbb{N}^*)^k$ a $k$-tuple of strictly positive integers. When $k \geq 2$, we assume they are coprime as a set. We define a function $P : \mathbb{N} \rightarrow \mathbb{C}$ by setting for all $n \in \mathbb{N}$: $$P(n) = \operatorname{Card}\left\{(n_1, \ldots, n_k) \in \mathbb{N}^k : n_1 a_1 + \cdots + n_k a_k = n\right\}.$$ We assume $k = 2$. We set $a = a_1, b = a_2, \omega_a = \exp(2\mathrm{i}\pi/a), \omega_b = \exp(2\mathrm{i}\pi/b)$. From a partial fraction decomposition of the fraction $\frac{1}{(1 - x^a)(1 - x^b)}$, show the formula $$P(n) = \frac{1}{2a} + \frac{1}{2b} + \frac{n}{ab} + \frac{1}{a} \sum_{j=1}^{a-1} \frac{\omega_a^{-jn}}{1 - \omega_a^{jb}} + \frac{1}{b} \sum_{k=1}^{b-1} \frac{\omega_b^{-kn}}{1 - \omega_b^{ka}}$$ for all integer $n \geq 0$.
Q11 Number Theory Linear Diophantine Equations View
Let $k \in \mathbb{N}^*$ and $(a_1, \ldots, a_k) \in (\mathbb{N}^*)^k$ a $k$-tuple of strictly positive integers. When $k \geq 2$, we assume they are coprime as a set. We define a function $P : \mathbb{N} \rightarrow \mathbb{C}$ by setting for all $n \in \mathbb{N}$: $$P(n) = \operatorname{Card}\left\{(n_1, \ldots, n_k) \in \mathbb{N}^k : n_1 a_1 + \cdots + n_k a_k = n\right\}.$$ We assume $k = 2$. Prove that $$P(n) = \frac{n}{ab} - \left\{\frac{b^* n}{a}\right\} - \left\{\frac{a^* n}{b}\right\} + 1$$ for all integer $n \geq 0$, where $a^*$ and $b^*$ are integers satisfying $a^* a = 1$ modulo $b$ and $b^* b = 1$ modulo $a$ respectively.
Hint. One may use the formula $(*)$ for $b = 1$.
Q12 Proof Proof of Set Membership, Containment, or Structural Property View
Let $n \geq 1$ be an integer. A non-empty compact subset $P \subset \mathbb{R}^n$ is a polytope if there exist a non-empty finite set $I$ and if for all $i \in I$ there exist a linear form $\ell_i : \mathbb{R}^n \rightarrow \mathbb{R}$ and a real number $a_i \in \mathbb{R}$ such that $P = \{x \in \mathbb{R}^n : \ell_i(x) \leq a_i\ \forall i \in I\}$. A face $F$ of $P$ is a non-empty subset such that there exists $J \subset I$ with $F = F_J = \{x \in P : \ell_j(x) = a_j\ \forall j \in J\}$.
Verify that every face $F$ of $P$ is a polytope and that $\operatorname{dim} F < \operatorname{dim} P$ if $F \neq P$.
Q13 Matrices Linear Transformation and Endomorphism Properties View
Let $n \geq 1$ be an integer and $P \subset \mathbb{R}^n$ a polytope. Show that $P$ has a finite number of faces and at least one vertex.
Q14 Matrices Linear Transformation and Endomorphism Properties View
Let $n \geq 1$ be an integer and $P \subset \mathbb{R}^n$ a polytope. Let $V$ be the set of vertices of $P$. Show that $P = \operatorname{Conv}(V)$.
Q15 Matrices Linear Transformation and Endomorphism Properties View
Let $V \subset \mathbb{R}^n$ be a non-empty finite set. Justify that to prove that $\operatorname{Conv}(V)$ is a polytope it suffices to treat the case where $\operatorname{Conv}(V)$ is not contained in a hyperplane of $\mathbb{R}^n$ and contains 0 in its interior.
Q16 Proof Proof of Set Membership, Containment, or Structural Property View
Let $V \subset \mathbb{R}^n$ be a non-empty finite set. We assume that $\operatorname{Conv}(V)$ is not contained in a hyperplane of $\mathbb{R}^n$ and contains 0 in its interior. Show that the set $Q$ defined by $$Q = \left\{\ell \in \mathbb{R}^n : \langle \ell, x \rangle \leq 1 \quad \forall x \in V\right\}$$ is a polytope of $\mathbb{R}^n$.
Q17 Proof Deduction or Consequence from Prior Results View
Let $V \subset \mathbb{R}^n$ be a non-empty finite set. We assume that $\operatorname{Conv}(V)$ is not contained in a hyperplane of $\mathbb{R}^n$ and contains 0 in its interior, and that the set $Q = \{\ell \in \mathbb{R}^n : \langle \ell, x \rangle \leq 1\ \forall x \in V\}$ is a polytope of $\mathbb{R}^n$. Deduce that $\operatorname{Conv}(V)$ is a polytope.
Q18 Proof Proof of Set Membership, Containment, or Structural Property View
We will admit that for every non-empty closed convex set $C \subset \mathbb{R}^n$ and every $x \in \mathbb{R}^n \backslash C$, there exists a unique $y \in C$ such that $\langle x - y, z - y \rangle \leq 0$ for all $z \in C$.
Let $V \subset \mathbb{R}^n$ be a non-empty finite set. Prove that every vertex of $\operatorname{Conv}(V)$ belongs to $V$.
Q19 Proof Proof That a Map Has a Specific Property View
Let $\mathcal{F}_n$ be the $\mathbb{R}$-vector space of functions $f : \mathbb{R}^n \rightarrow \mathbb{R}$. For all $X \subset \mathbb{R}^n$, we denote $\mathbb{1}_X$ the indicator function of $X$. Let $\mathcal{U}_n$ be the vector subspace of $\mathcal{F}_n$ generated by the functions $\mathbb{1}_P$ where $P$ is a polytope of $\mathbb{R}^n$.
Let $f \in \mathcal{U}_1$. Prove that for all $x \in \mathbb{R}$ the limit of $f(y)$ as $y$ tends to $x$ while satisfying $y > x$, denoted $\lim_{y \rightarrow x^+} f(y)$, exists and that there exist finitely many reals $x \in \mathbb{R}$ such that $f(x) \neq \lim_{y \rightarrow x^+} f(y)$.
Q20 Proof Proof of Set Membership, Containment, or Structural Property View
Let $\mathcal{F}_n$ be the $\mathbb{R}$-vector space of functions $f : \mathbb{R}^n \rightarrow \mathbb{R}$. For all $X \subset \mathbb{R}^n$, we denote $\mathbb{1}_X$ the indicator function of $X$. Let $\mathcal{U}_n$ be the vector subspace of $\mathcal{F}_n$ generated by the functions $\mathbb{1}_P$ where $P$ is a polytope of $\mathbb{R}^n$.
We assume that $n > 1$. Let $f \in \mathcal{U}_n$. For $z \in \mathbb{R}$, we define the function $f_z : \mathbb{R}^{n-1} \rightarrow \mathbb{R}$ by $f_z(x_1, \ldots, x_{n-1}) = f(x_1, \ldots, x_{n-1}, z)$ for all $(x_1, \ldots, x_{n-1}) \in \mathbb{R}^{n-1}$. Prove that $f_z \in \mathcal{U}_{n-1}$.
Q21 Proof Proof That a Map Has a Specific Property View
Let $\mathcal{F}_n$ be the $\mathbb{R}$-vector space of functions $f : \mathbb{R}^n \rightarrow \mathbb{R}$. For all $X \subset \mathbb{R}^n$, we denote $\mathbb{1}_X$ the indicator function of $X$. Let $\mathcal{U}_n$ be the vector subspace of $\mathcal{F}_n$ generated by the functions $\mathbb{1}_P$ where $P$ is a polytope of $\mathbb{R}^n$.
Prove that the following definition allows us to define a linear form $\chi_n : \mathcal{U}_n \rightarrow \mathbb{R}$. We define $\chi_1(f)$ by the sum $\chi_1(f) = \sum_{x \in \mathbb{R}} \left(f(x) - \lim_{y \rightarrow x^+} f(y)\right)$, then for $f \in \mathcal{U}_n$ with $n > 1$, we set $$\chi_n(f) = \chi_1(g) \text{ with } g \text{ defined by } g(z) = \chi_{n-1}(f_z) \text{ for } z \in \mathbb{R}.$$ We will show at the same time the formula $\chi_n(\mathbb{1}_P) = 1$ for every polytope $P$ of $\mathbb{R}^n$ and we will justify that $\chi_n$ is independent of the coordinate system, namely that for every invertible linear map $A : \mathbb{R}^n \rightarrow \mathbb{R}^n$ we have $\chi_n(f \circ A) = \chi_n(f)$ for all $f \in \mathcal{U}_n$.
Q22 Proof Existence Proof View
Let $\mathcal{U}_n$ be the vector subspace of functions $\mathbb{R}^n \rightarrow \mathbb{R}$ generated by indicator functions of polytopes of $\mathbb{R}^n$. For a polytope $P$ of $\mathbb{R}^n$, the relative interior $P^\circ$ is defined as $P^\circ = \{x \in P : \ell_i(x) = a_i \Leftrightarrow i \in S_F\}$ where $S_F = \{i \in I, \ell_i(x) = a_i\ \forall x \in F\}$.
Show that for every polytope $P$ of $\mathbb{R}^n$ and for all $x \in P \backslash P^\circ$, there exists a face $F \subset P$ such that $F \neq P$ and $x \in F$.
Q23 Proof Direct Proof of a Stated Identity or Equality View
Let $\mathcal{U}_n$ be the vector subspace of functions $\mathbb{R}^n \rightarrow \mathbb{R}$ generated by indicator functions of polytopes of $\mathbb{R}^n$, and $\chi_n : \mathcal{U}_n \rightarrow \mathbb{R}$ the linear form defined recursively. For a polytope $P$ of $\mathbb{R}^n$, let $P^\circ$ denote its relative interior.
Show that for every polytope $P$ of $\mathbb{R}^n$, $\mathbb{1}_{P^\circ} \in \mathcal{U}_n$ and $\chi_n(\mathbb{1}_{P^\circ}) = (-1)^{\operatorname{dim} P}$.
Q24 Proof Deduction or Consequence from Prior Results View
Let $\mathcal{U}_n$ be the vector subspace of functions $\mathbb{R}^n \rightarrow \mathbb{R}$ generated by indicator functions of polytopes of $\mathbb{R}^n$, and $\chi_n : \mathcal{U}_n \rightarrow \mathbb{R}$ the linear form defined recursively, satisfying $\chi_n(\mathbb{1}_{P^\circ}) = (-1)^{\operatorname{dim} P}$ for every polytope $P$.
Deduce Euler's formula $\sum_F (-1)^{\operatorname{dim} F} = 1$ where $F$ ranges over the faces of $P$.
Q25 Proof Proof of Set Membership, Containment, or Structural Property View
A complex is a non-empty finite set $\mathcal{C}$ of polytopes of $\mathbb{R}^n$ such that for all $P, Q \in \mathcal{C}$, $P \cap Q$ is either empty or simultaneously a face of both $P$ and $Q$. A face of $\mathcal{C}$ is a subset $F \subset |\mathcal{C}|$ that is a face of one of the $P \in \mathcal{C}$.
Show that if $P$ is a polytope of $\mathbb{R}^n$ of dimension $k > 0$, the set of its faces of dimension $k-1$ forms a complex.
Q26 Proof Proof of Set Membership, Containment, or Structural Property View
A complex is a non-empty finite set $\mathcal{C}$ of polytopes of $\mathbb{R}^n$ such that for all $P, Q \in \mathcal{C}$, $P \cap Q$ is either empty or simultaneously a face of both $P$ and $Q$.
Let $P$ be a polytope of $\mathbb{R}^n$ of dimension $k > 0$ and $x \in P^\circ$. For each face $F$ of dimension $k-1$ of $P$ we denote $F_x = \operatorname{Conv}(F \cup \{x\})$. Show that the family of $F_x$ forms a complex whose realization equals $P$.
Q27 Proof Existence Proof View
A triangulation of a polytope $P$ is a complex formed of simplices whose realization equals $P$. Show that every polytope admits a triangulation.
Q28 Proof Direct Proof of a Stated Identity or Equality View
A complex $\mathcal{C}$ is a non-empty finite set of polytopes of $\mathbb{R}^n$ such that for all $P, Q \in \mathcal{C}$, $P \cap Q$ is either empty or simultaneously a face of both $P$ and $Q$. We denote $\chi(\mathcal{C}) = \sum_F (-1)^{\operatorname{dim} F}$ where $F$ ranges over the faces of $\mathcal{C}$.
Show that every complex $\mathcal{C}$ whose realization is convex satisfies $\chi(\mathcal{C}) = 1$.
Q29 Proof Characterization or Determination of a Set or Class View
Let $n \geq 1$ be an integer. We say that a matrix $M \in \mathcal{M}_n(\mathbb{R})$ is doubly stochastic if for all $i, j \in \{1, \ldots, n\}$ we have $$M_{ij} \geq 0 \quad \text{and} \quad \sum_{k=1}^n M_{ik} = \sum_{k=1}^n M_{kj} = 1.$$ We denote by $B_n$ the set of doubly stochastic matrices in $\mathcal{M}_n(\mathbb{R})$.
Show that $B_n$ is a polytope and determine its dimension.
Q30 Proof Proof of Set Membership, Containment, or Structural Property View
Let $n \geq 1$ be an integer. We denote by $B_n$ the set of doubly stochastic matrices in $\mathcal{M}_n(\mathbb{R})$ and $S_n$ the symmetric group of order $n$. For all $\sigma \in S_n$, we define $P^\sigma \in \mathcal{M}_n(\mathbb{R})$ as follows: for $i, j \in \{1, 2, \ldots, n\}$ we set $P^\sigma_{ij} = 1$ if $j = \sigma(i)$, $P^\sigma_{ij} = 0$ otherwise. Show that $P^\sigma$ is a vertex of $B_n$ for all $\sigma \in S_n$.
Q31 Proof Existence Proof View
Let $n \geq 1$ be an integer. We denote by $B_n$ the set of doubly stochastic matrices in $\mathcal{M}_n(\mathbb{R})$ and $\mathcal{M}_n(\mathbb{Z})$ the set of $n \times n$ matrices with integer coefficients.
Suppose that $M \in B_n \backslash \mathcal{M}_n(\mathbb{Z})$. Show that there exists a sequence $(r_1, s_1), (r_2, s_2), \ldots, (r_k, s_k)$ of pairs of indices with $k \geq 2$ such that $$0 < M_{r_i, s_i} < 1, \quad 0 < M_{r_i, s_{i+1}} < 1 \quad \text{and} \quad (r_k, s_k) = (r_1, s_1)$$ then that we can assume that all the pairs $(r_1, s_1), (r_1, s_2), (r_2, s_2), \ldots, (r_{k-1}, s_{k-1}), (r_{k-1}, s_k)$ are distinct.
Q32 Proof Deduction or Consequence from Prior Results View
Let $n \geq 1$ be an integer. We denote by $B_n$ the set of doubly stochastic matrices in $\mathcal{M}_n(\mathbb{R})$ and $\mathcal{M}_n(\mathbb{Z})$ the set of $n \times n$ matrices with integer coefficients.
Suppose that $M \in B_n \backslash \mathcal{M}_n(\mathbb{Z})$. Deduce that there exists a nonzero matrix $Q$ and $\epsilon > 0$ such that $\{M + tQ, t \in [-\epsilon, \epsilon]\} \subset B_n$, and conclude that every vertex of $B_n$ is of the form $P^\sigma$.
Q33 Proof Proof of Set Membership, Containment, or Structural Property View
Let $n \geq 1$ be an integer. We denote by $\mathbb{C}[[\mathbb{Z}^n]]$ the $\mathbb{C}$-vector space of functions $f : \mathbb{Z}^n \rightarrow \mathbb{C}$. We say that $f \in \mathbb{C}[[\mathbb{Z}^n]]$ is rational if there exists a nonzero $P \in \mathbb{C}[\mathbb{Z}^n]$ such that $Pf \in \mathbb{C}[\mathbb{Z}^n]$. We say that $f$ is torsion if there exists a nonzero $P \in \mathbb{C}[\mathbb{Z}^n]$ such that $Pf = 0$. We denote by $\mathcal{R}$ the $\mathbb{C}$-vector space of rational elements and $\mathcal{T}$ the $\mathbb{C}$-vector space of torsion elements of $\mathbb{C}[[\mathbb{Z}^n]]$.
In the case where $n = 1$, show that the inclusions $0 \subset \mathcal{T} \subset \mathcal{R} \subset \mathbb{C}[[\mathbb{Z}^n]]$ are strict.
Q34 Proof Proof That a Map Has a Specific Property View
Let $n \geq 1$ be an integer. We denote by $\mathbb{C}[[\mathbb{Z}^n]]$ the $\mathbb{C}$-vector space of functions $f : \mathbb{Z}^n \rightarrow \mathbb{C}$, $\mathcal{R}$ the $\mathbb{C}$-vector space of rational elements, $\mathcal{T}$ the $\mathbb{C}$-vector space of torsion elements, and $\mathbb{C}(\mathbb{Z}^n)$ the field of fractions of $\mathbb{C}[\mathbb{Z}^n]$.
We define a $\mathbb{C}$-linear map $\mathrm{I} : \mathcal{R} \rightarrow \mathbb{C}(\mathbb{Z}^n)$ as follows. If $f \in \mathcal{R}$ satisfies $Qf = P$ with $P, Q \in \mathbb{C}[\mathbb{Z}^n]$, we set $\mathrm{I}(f) = \frac{P}{Q}$. Show that $\mathrm{I}$ is well defined, and that it is a linear map with kernel $\mathcal{T}$ satisfying $\mathrm{I}(Pf) = P\,\mathrm{I}(f)$ for all $f \in \mathcal{R}$ and $P \in \mathbb{C}[\mathbb{Z}^n]$.
Q35 Proof Existence Proof View
Let $n \geq 1$ be an integer. Let $\mathbb{C}[[\mathbb{Z}^n]]$, $\mathcal{R}$, $\mathbb{C}(\mathbb{Z}^n)$, and $\mathrm{I} : \mathcal{R} \rightarrow \mathbb{C}(\mathbb{Z}^n)$ be as defined previously.
Let $u : \mathbb{Z}^n \rightarrow \mathbb{R}$ be an injective group homomorphism. Show that there exists a unique map $s_u : \mathbb{C}(\mathbb{Z}^n) \rightarrow \mathcal{R}$ satisfying the following three conditions:
  • [(a)] $s_u(Pf) = P\,s_u(f)$ for all $f \in \mathbb{C}(\mathbb{Z}^n)$ and $P \in \mathbb{C}[\mathbb{Z}^n]$.
  • [(b)] $\mathrm{I}(s_u(f)) = f$ for all $f \in \mathbb{C}(\mathbb{Z}^n)$.
  • [(c)] $s_u\left(\frac{1}{1-g}\right) = \sum_{n \in \mathbb{N}} g^n$ if $g$ is a finite linear combination of elements of the form $x^\gamma$ with $\gamma \in \mathbb{Z}^n$ satisfying $u(\gamma) > 0$.
Q36 Proof Direct Proof of a Stated Identity or Equality View
Let $n \geq 1$ be an integer. For $A \subset \mathbb{R}^n$, let $E_A = \sum_{\gamma \in A \cap \mathbb{Z}^n} x^\gamma \in \mathbb{C}[[\mathbb{Z}^n]]$.
Show that if $A$ and $B$ are two subsets of $\mathbb{R}^n$ and $\gamma \in \mathbb{Z}^n$ we have $$E_{A \cup B} + E_{A \cap B} = E_A + E_B \quad \text{and} \quad E_{\gamma + A} = x^\gamma E_A.$$
Q37 Proof Proof of Set Membership, Containment, or Structural Property View
Let $n \geq 1$ be an integer. For $A \subset \mathbb{R}^n$, let $E_A = \sum_{\gamma \in A \cap \mathbb{Z}^n} x^\gamma \in \mathbb{C}[[\mathbb{Z}^n]]$.
Let $\gamma_1, \ldots, \gamma_k$ be a family of vectors in $\mathbb{Z}^n \subset \mathbb{R}^n$ and $$C(\gamma_1, \ldots, \gamma_k) = \left\{\sum_{i=1}^k t_i \gamma_i : (t_1, \ldots, t_k) \in [0, +\infty[^k\right\}.$$ Show that if $\gamma_1, \ldots, \gamma_k$ is a free family, $E_{v + C(\gamma_1, \ldots, \gamma_k)}$ is rational for all $v \in \mathbb{R}^n$.
Q38 Proof Proof of Set Membership, Containment, or Structural Property View
Let $n \geq 1$ be an integer. For $A \subset \mathbb{R}^n$, let $E_A = \sum_{\gamma \in A \cap \mathbb{Z}^n} x^\gamma \in \mathbb{C}[[\mathbb{Z}^n]]$. Let $$C(\gamma_1, \ldots, \gamma_k) = \left\{\sum_{i=1}^k t_i \gamma_i : (t_1, \ldots, t_k) \in [0, +\infty[^k\right\}.$$
Generalize the previous question in the case where $\gamma_1, \ldots, \gamma_k \in \mathbb{Z}^n$ is a family of vectors not necessarily free but for which there exists a linear form $\ell : \mathbb{R}^n \rightarrow \mathbb{R}$ such that $\ell(\gamma_i) > 0$ for $i = 1, \ldots, k$.
Hint. One may triangulate the polytope $P = \{x \in C(\gamma_1, \ldots, \gamma_k) : \ell(x) = 1\}$.