Tag: prove

Differential equation dx/dt=kx^2 prove that I have all the solutions

In the book Differential Equations and Boundary Value Problems by Edwards and Penney, section 1.1, question 43, a differential equation is provided:

$ $ \frac{dx}{dt} = kx^2\ $ $

and a solution:

$ $ x(t)=\frac{1}{C-kt}. $ $

The question then says “Determine by inspection a solution of the initial value problem $ x’=kx^2, x(0)=0.$ “

I reason that since the provided solution never equals $ 0$ , I can safely ignore it. Also, if $ x=0$ , then $ x’=0$ , which means that only the functions which might be solutions are ones that have a local min or max at the point $ (0,0)$ .

The answer in the back of the book is given as the identically zero function. This makes me squint, since while that clearly is a solution, I don’t see how to prove that it’s the only one. At this point, I realize that the question does say a solution, and not every solution, so I guess it works as an answer to the question, but now I’m still left wondering if the identically zero function is in fact the only solution that satisfies that initial condition, and more particularly, how to prove it, if it’s true.

I see how to achieve the solution for all $ x$ where $ x\neq 0$ , so that part is clear to me. I just don’t see how to go from “the point $ (t,0)$ must be a local extremum if it solves $ x$ ” to “$ x$ is identically $ 0$ “, or actually, if that conclusion is even true.

Either find a perfect matching, or prove that none exist

I am looking for a polynomial-time algorithm that takes as input a bipartite graph, and returns one of two options:

  1. If a perfect matching exists, it returns the matching;

  2. Otherwise, it returns an “evidence” that a perfect matching does not exist, based on Hall’s theorem, i.e., it returns a set $ X$ such that the number of neighbors of $ X$ is smaller than $ |X|$ .

I found in wikipedia various algorithms for finding a maximum matching in an unweighted bipartite graph. Such algorithms can be used to determine if a perfect matching exists. But does any of these algorithms also return an evidence in case of failure?

How to prove a set of delay differential equations never converge (the delay is not constant)

Two functions $ x(t)$ and $ y(t)$ are coupled via: $ $ \dot X(t) = a Y(t)-b,Y(t+X(t))=X(t)$ $

where $ a<0, b$ is a constant.

I am mostly confused with the second equation. What is the mathematical term for this kind of delay differential equation? What kind of initial condition do I need to specify?

It is obvious that, if $ X(0)=Y(0)=b/a$ , then the system will stay stable for all $ t>0$ .

Through doing some simulation also back of envelope thinking, it seems that when $ X(0)=Y(0)=0$ , then the system may never converge to an equilibrium/stable solution. However, I have no idea what type of proof technique is required to show that.

Thanks!

How to prove a matrix is positive semidefinite

Let $ X\in S^3_+$ be a semidefinite cone. Show the explicit conditions on the components of $ X$ .

I wanted to show for a positive semidefenit matrix $ X$ we have $ z^T Xz\geq0\forall z$ :

$ $ \begin{bmatrix} z_1& z_2& z_3 \end{bmatrix}\begin{bmatrix} x_1& x_2& x_3\x_2& x_4& x_5\x_3& x_5& x_6 \end{bmatrix}\begin{bmatrix} z_1\z_2\z_3 \end{bmatrix}=z_1^2x_1+2z_1z_2x_2+2z_1z_3x_3+z_2^2x_4+z_3z_2x_5+z_3^2x_6\geq 0 \forall z$ $

This is the point where I am lost. I have seen people continue by assuming $ x_1=0$ and deducing $ x_2=x_3=0$ so that $ X\succeq0$ iff $ \begin{bmatrix} x_4& x_5\x_5& x_6\end{bmatrix}\succeq0$ , but I do not understand why is this true? Surly, I did not understand the next part of if $ x_1\neq 0$

How to prove length of smooth curve

Suppose there is a smooth curve $ L(t)=\begin{cases}x(t)\y(t)\end{cases},\ t\in[a,b]\subset R$ with continues first derivative.

To find the length of $ L$ we separate $ L$ into several small part $ l_i$ .

Define the arc length of $ l_i$ is $ s_i$ and the length of the straight line connecting the 2 end points of $ l_i$ is $ d_i$ .

Now my question is how to prove that $ s_i=d_i+o(d_i)$ where $ \lim_{d_i\to0}o(d_i)=0$ .

In other words, $ d_i$ converges to $ s_i$ when it becomes infinitely small. Which is the base that allows me to use integration to find the length.

Furthermore, does it has to be smooth curve? What about other non-normal curves (like those everywhere continuous, nowhere derivable functions)?

Thanks a lot!

prove that there is a linear ordering of G that puts v before w if and only if there is no path in G from w to v

Let G’ be the graph G with an edge e added from v to w. We note that a linear ordering of the form we are looking for must respect all edges of G and the edge e. Thus, we have a linear ordering of G with v coming before w if and only if there is a linear ordering of G’. We know that G’ can be linearly ordered if and only if it is a DAG. We know that G has no cycles, therefore any cycle of G’ must contain the edge e. Such a cycle must contain e along with a path from w to v in G, and any such path can be made into a cycle in G’. Therefore there is such an ordering if and only if G’ is a DAG, which in turn is if and only if there is no path in G from w to v.

Prove complement a^nb^nc^n is contextfree

So the complement of L1 = {$ a^{n}b^{n}c^{n}$ | n $ \geq$ 1} would be L2 = {a,b,c}* \ {$ a^{n}b^{n}c^{n}$ | n $ \geq$ 1}.

In other words, any combinations of a,b and c where we dont have an equal number of all three letters and w = $ \varepsilon$ is also legit.

However, while I’m certain that there should be a contextfree grammar for L2, I can’t seem to find a grammer that allows you to generate the terminals freely without allowing $ a^{n}b^{n}c^{n}$ with n $ \geq$ 1.

My attempt was to make a starting Rule S -> $ Q_{_{a}}$ ; $ Q_{_{b}}$ ; $ Q_{_{c}}$ ; $ \varepsilon$ so that the individual Q rules would make it possible for two of the terminals a, b and c to have an equal number, but not for the third. (in $ Q_{_{a}}$ , a is restricted by max(b,c), in $ Q_{_{b}}$ , b is restricted by max(a,c), in $ Q_{_{c}}$ , c is restricted by max(a,b) so that the restricted terminal can never show up as often as the unrestricted terminal with the highest count)

The rules I set up though, only allow to have unlimited numbers of unrestricted terminals in any order. I’m not sure how to implement a rule for the restricted terminal, without allowing it to have as high a count as the unrestricted ones, if the unrestricted ones have the same count.

here’s my P for G$ _{_{L2}}$ so far

S $ \rightarrow$ $ Q_{_{a}}$ ; $ Q_{_{b}}$ ; $ Q_{_{c}}$ ; $ \varepsilon$

$ Q_{_{a}}$ $ \rightarrow$ $ Q_{_{a}}$ b $ Q_{_{a}}$ ; $ Q_{_{a}}$ c $ Q_{_{a}}$ ; $ \varepsilon$

$ Q_{_{b}}$ $ \rightarrow$ $ Q_{_{b}}$ a $ Q_{_{b}}$ ; $ Q_{_{b}}$ c $ Q_{_{b}}$ ; $ \varepsilon$

$ Q_{_{c}}$ $ \rightarrow$ $ Q_{_{c}}$ a $ Q_{_{c}}$ ; $ Q_{_{c}}$ b $ Q_{_{c}}$ ; $ \varepsilon$

These are still missing the rules for the individual restricted variable. In what fashion can I add those, without breaking the [ $ a^{n}b^{n}c^{n}$ | n = 0 ] rule?

Edit: it occured to me that I could refine the restricting rules, such that the restricted terminal can be derived from a rule if, and only if one (and only one) of the unrestricted ones is always created with it. For example:

S $ \rightarrow$ $ Q_{_{a}}$ ; $ Q_{_{b}}$ ; $ Q_{_{c}}$ ; $ \varepsilon$

$ Q_{_{a}}$ $ \rightarrow$ $ Q_{_{ab}}$ b $ Q_{_{ab}}$ ; $ Q_{_{ac}}$ c $ Q_{_{ac}}$

$ Q_{_{ab}}$ $ \rightarrow$ $ Q_{_{ab}}$ b $ Q_{_{ab}}$ ; $ Q_{_{ab}}$ c $ Q_{_{ab}}$ ; $ Q_{_{ab}}$ a $ Q_{_{ab}}$ b $ Q_{_{ab}}$ ; $ Q_{_{ab}}$ b $ Q_{_{ab}}$ a $ Q_{_{ab}}$ ; $ \varepsilon$

$ Q_{_{ac}}$ $ \rightarrow$ $ Q_{_{ac}}$ b $ Q_{_{ac}}$ ; $ Q_{_{ac}}$ c $ Q_{_{ac}}$ ; $ Q_{_{ac}}$ a $ Q_{_{ac}}$ c $ Q_{_{ac}}$ ; $ Q_{_{ac}}$ c $ Q_{_{ac}}$ a $ Q_{_{ac}}$ ; $ \varepsilon$

At this point my brain starts running in circles. Would this set me on the right path?

Can I prove my type of UK citizenship with my passport?

I have full British citizenship.

My infant daughter was born abroad and is therefore British by descent – I have passed my citizenship to her, but she cannot pass it on (unless she goes through the naturalisation process also).

My question is: Can my type of British citizenship be determined directly from my passport, for instance from the passport number or another code?

If so, the passport and her identity card would prove she is a British citizen. (If not, the passport would only prove I am British by descent, in which case she would need her own passport to prove her citizenship).