If the center violates a constraint, choose a row with . Under the assumption of nonempty , this row cannot have . Every satisfies . Thus the central half-space
contains , and the given outer bound yields . Checking the rows of therefore supplies a separation oracle. If a violated row has zero normal, it instead certifies that is empty.
Whiten the ellipsoid by and rotate the cut normal to . The normalized current ellipsoid is the unit ball centered at zero. In the stated covering ellipsoid, for , the shape matrix has eigenvalue in the direction and in each of the other directions. The center does not affect volume, so
Using for and for gives
Therefore
This is the central-cut ellipsoid volume bound. Affine transformations preserve the ratio. The displayed matrix formula is undefined when ; in that case interval bisection gives the stronger ratio .
Undoing the normalization gives the general central-cut update
It preserves containment of the feasible region while reducing volume geometrically. After cuts the volume is less than . If a feasible region has a known positive-volume lower bound , more than unsuccessful cuts would be impossible. For rational inputs, outer-radius and positive-volume bounds of exponential size in a polynomial of the bit length therefore translate into a polynomial iteration count.
For a full ellipsoid method proof, two qualifications matter. A nonempty rational polyhedron may be lower-dimensional and have zero volume, so shrinking below a volume threshold alone cannot certify its emptiness. One uses a bounded-feasibility reduction and a sufficiently small rational relaxation or an affine-hull treatment, with input-dependent rational separation bounds. Also ellipsoid updates involve square roots, so a bit-complexity proof rounds with controlled outward error to preserve containment and a fixed volume decrease. With these precision bounds, and the polynomial-time row separation oracle here, the method establishes polynomial-time linear programming. The volume calculation is its essential geometric step, not by itself the entire complexity proof.
An integer program for the travelling salesman problem must exclude disconnected cycle covers, not merely require one incoming and one outgoing edge. Here is a compact order formulation of the travelling salesman problem. The one-city case is trivial. For , use binary variables for directed edges, , and integer variables for . Minimize subject to
The degree equations give a collection of disjoint directed cycles. Along any selected edge between nondistinguished cities, the last inequality gives . Summing around a cycle avoiding city would yield for its positive length . Thus every cycle must contain city , so there is exactly one tour. Conversely, number the cities after city in tour order, giving . Selected edges satisfy the order inequalities. Unselected edges impose no additional restriction, since . This proves equivalence with tours, including symmetric-distance instances represented by directed variables.
There are variables and rows. For the bit count, store only nonzero coefficients and their indices. The degree equations have entries in total; each order inequality has three entries, so these too have entries. Indices and the coefficients bounded by need bits each. The objective has distance coefficients, each needing at most bits because the PDF's bound is . Therefore
Writing an unnecessarily dense constraint matrix would give a larger encoding; it is the sparse explicit encoding that establishes the requested bound. For the decision version add . A threshold can be capped at , so its relevant binary length is ; negative thresholds can be rejected immediately for nonnegative distances.
A decision problem belongs to NP if its yes-instances have certificates of polynomial length checkable in deterministic polynomial time. It is NP-complete if it belongs to NP and every NP problem has a polynomial-time many-one reduction to it. The preceding construction is a polynomial-time reduction from travelling-salesman decision to integer-linear feasibility. If the former is NP-complete, the latter is consequently NP-hard.
For completeness we must also establish membership in NP for general integer-linear feasibility, rather than just for the binary instances produced by the reduction. An arbitrary feasible integer assignment could be numerically enormous; what is needed is the existence of a short one. We give a small integer feasibility witness by homogeneous cone decomposition.
Split each unrestricted integer variable into the difference of two nonnegative integer variables and add nonnegative integer slacks to inequalities. This gives , , with variables and integer data bounded in absolute value by . Both and are polynomially bounded by the original input length. Consider the homogeneous cone
Every vector in this cone is a nonnegative combination of at most support-minimal rays. To prove this, choose a nonnegative kernel vector of minimal nonempty support contained in the support of a given vector, subtract with the smallest positive coordinate ratio, and repeat. Each subtraction strictly reduces support. On a minimal support the kernel is one-dimensional: an independent kernel direction would let us perturb a positive vector to the boundary of its support without making it zero, contradicting minimality. Cofactors of independent rows therefore give an integer nonnegative generator of each such ray. Every coordinate is bounded by
using the elementary determinant bound. This proves the needed support-minimal rays of a nonnegative kernel facts directly.
Start with any integer feasible and decompose in this way. A ray whose last coordinate is a positive integer normalizes to a point with and ; the coefficients of these normalized points sum to one. Rays with last coordinate zero have integer nonnegative first coordinates with and coordinates at most . Hence
with at most ray terms. Subtract from . The result is still integer, nonnegative and feasible, and satisfies
Its binary length is polynomial, since . The assignment can be checked by exact integer arithmetic in polynomial time. Thus general integer-linear feasibility is in NP. Combining this with the reduction proves
Introduce nonnegative slack variables , and , and write the objective as . With nonbasic, the initial simplex dictionary is
This is feasible at the origin. Enter . The simplex ratio test selects to leave, since its bound is , compared with from . Pivoting gives
Now enter . The ratio test chooses to leave: its bound is smaller than from and from . The resulting dictionary is
All basic values are nonnegative and all nonbasic objective coefficients are nonpositive. The simplex algorithm therefore certifies
The negative objective coefficients also make this continuous optimum unique.
For integer , all three original slacks are integers. Apply a Gomory fractional cut to the row
The fractional part of is , so the cut is , or . To justify it directly, rewrite the row as
The parenthesized term is an integer and is at most , since the other term is nonnegative. It is therefore at most , proving the cut. This retains every feasible integer solution and excludes the current fractional optimum. Since , the cut is equivalently .
Introduce the integer-valued nonnegative slack . Its dictionary row is , so primal feasibility fails while the objective row remains dual feasible. In the dual simplex algorithm, leaves; tie in the dual ratio test, each with ratio . Choose to enter. Substituting gives
This dictionary is feasible at and certifies the cut relaxation's optimum , achieved at the integer point .
To find every optimal integer point, the objective row forces . Nonnegativity of all the remaining rows then reduces to . On this optimal edge, . Since must be integral, only its two endpoints are possible:
Give its Adjoint representation and use the tensor product of Lie algebra representations. Define the action map of a Lie algebra representation
For , the action on the source is . The defining representation identity then gives
Thus is a Lie algebra representation homomorphism.
If is nontrivial and simple, the action is not identically zero, so the image of is a nonzero submodule. Simplicity forces to be surjective. For a finite-dimensional and a semisimple Lie algebra, the Weyl complete reducibility theorem provides an invariant complement to in . The restriction is then an isomorphism onto , giving
This proves the requested summand assertion in the finite-dimensional setting.
If finite dimensionality is not implicit, the final assertion needs that hypothesis: the action summand can fail for an infinite-dimensional simple module. Here is an explicit counterexample. Take with , , , and the Verma module of highest weight :
The lowering coefficient never vanishes for , so an invariant subspace, using the distinct -weights to isolate a basis vector and then raising, contains and hence all of . Thus is simple.
In , a vector of weight is . Applying gives , so its highest vectors are precisely the multiples of . But , and has weight zero, absent from . Every homomorphism therefore kills this vector and then kills . Any embedded copy of would send its highest vector to a nonzero multiple of , so it cannot admit a projection back to . This rules out a direct summand, not merely a splitting of the particular action map.

Pinned article: Introduction to the OurBigBook Project

Welcome to the OurBigBook Project! Our goal is to create the perfect publishing platform for STEM subjects, and get university-level students to write the best free STEM tutorials ever.
Everyone is welcome to create an account and play with the site: ourbigbook.com/go/register. We belive that students themselves can write amazing tutorials, but teachers are welcome too. You can write about anything you want, it doesn't have to be STEM or even educational. Silly test content is very welcome and you won't be penalized in any way. Just keep it legal!
We have two killer features:
  1. topics: topics group articles by different users with the same title, e.g. here is the topic for the "Fundamental Theorem of Calculus" ourbigbook.com/go/topic/fundamental-theorem-of-calculus
    Articles of different users are sorted by upvote within each article page. This feature is a bit like:
    • a Wikipedia where each user can have their own version of each article
    • a Q&A website like Stack Overflow, where multiple people can give their views on a given topic, and the best ones are sorted by upvote. Except you don't need to wait for someone to ask first, and any topic goes, no matter how narrow or broad
    This feature makes it possible for readers to find better explanations of any topic created by other writers. And it allows writers to create an explanation in a place that readers might actually find it.
    Figure 1.
    Screenshot of the "Derivative" topic page
    . View it live at: ourbigbook.com/go/topic/derivative
  2. local editing: you can store all your personal knowledge base content locally in a plaintext markup format that can be edited locally and published either:
    This way you can be sure that even if OurBigBook.com were to go down one day (which we have no plans to do as it is quite cheap to host!), your content will still be perfectly readable as a static site.
    Figure 5. . You can also edit articles on the Web editor without installing anything locally.
    Video 3.
    Edit locally and publish demo
    . Source. This shows editing OurBigBook Markup and publishing it using the Visual Studio Code extension.
  3. https://raw.githubusercontent.com/ourbigbook/ourbigbook-media/master/feature/x/hilbert-space-arrow.png
  4. Infinitely deep tables of contents:
    Figure 6.
    Dynamic article tree with infinitely deep table of contents
    .
    Descendant pages can also show up as toplevel e.g.: ourbigbook.com/cirosantilli/chordate-subclade
All our software is open source and hosted at: github.com/ourbigbook/ourbigbook
Further documentation can be found at: docs.ourbigbook.com
Feel free to reach our to us for any help or suggestions: docs.ourbigbook.com/#contact