Threefish

2013-11-23T12:57:53Z

174.52.255.118: Explicit reference to Threefish being a symmetric-key cipher

{{Expert-subject|Mathematics|date=November 2008}}
In [[control theory]], a '''Kalman decomposition''' provides a mathematical means to convert a representation of any [[LTI system theory|linear time-invariant]] [[control system]] to a form in which the system can be decomposed into a standard form which makes clear the [[Observability|observable]] and [[Controllability|controllable]] components of the system. This decomposition results in the system being presented with a more illuminating structure, making it easier to draw conclusions on the system's [[Reachability problem|reachable]] and observable subspaces.

== Notation ==
The derivation is identical for both discrete-time as well as continuous time LTI systems. The description of a continuous time linear system is

: <math>\dot{x}(t) = Ax(t) + Bu(t)</math>
: <math>\, y(t) = Cx(t) + Du(t)</math>

where
: <math>\, x</math> is the "state vector",
: <math>\, y</math> is the "output vector",
: <math>\, u</math> is the "input (or control) vector",
: <math>\, A</math> is the "state matrix",
: <math>\, B</math> is the "input matrix",
: <math>\, C</math> is the "output matrix",
: <math>\, D</math> is the "feedthrough (or feedforward) matrix".

Similarly, a discrete-time linear control system can be described as

: <math>\, x(k+1) = Ax(k) + Bu(k)</math>
: <math>\, y(k) = Cx(k) + Du(k)</math>

with similar meanings for the variables. Thus, the system can be described using the tuple consisting of four matrices <math>\, (A, B, C, D)</math>.
Let the order of the system be <math>\, n</math>.

Then, the Kalman decomposition is defined as a transformation of the tuple <math>\, (A, B, C, D)</math> to <math>\, (\hat{A}, \hat{B}, \hat{C}, \hat{D})</math> as follows:

: <math>\, {\hat{A}} = {T^{-1}}AT</math>
: <math>\, {\hat{B}} = {T^{-1}}B</math>
: <math>\, {\hat{C}} = CT</math>
: <math>\, {\hat{D}} = D</math>

<math>\, T</math> is an <math>\, n \times n</math> invertible matrix defined as

: <math>\, T = \begin{bmatrix} T_{r\overline{o}} & T_{ro} & T_{\overline{ro}} & T_{\overline{r}o}\end{bmatrix}</math>

where
* <math>\, T_{r\overline{o}}</math> is a matrix whose columns span the subspace of states which are both reachable and unobservable.
* <math>\, T_{ro}</math> is chosen so that the columns of <math>\, \begin{bmatrix} T_{r\overline{o}} & T_{ro}\end{bmatrix}</math> are a basis for the reachable subspace.
* <math>\, T_{\overline{ro}}</math> is chosen so that the columns of <math>\, \begin{bmatrix} T_{r\overline{o}} & T_{\overline{ro}}\end{bmatrix}</math> are a basis for the unobservable subspace.
* <math>\, T_{\overline{r}o}</math> is chosen so that <math>\,\begin{bmatrix} T_{r\overline{o}} & T_{ro} & T_{\overline{ro}} & T_{\overline{r}o}\end{bmatrix}</math> is invertible.
By construction, the matrix <math>\, T</math> is invertible. It can be observed that some of these matrices may have dimension zero. For example, if the system is both observable and controllable, then <math>\, T = T_{ro}</math>, making the other matrices zero dimension.

==Standard Form==
By using results from controllability and observability, it can be shown that the transformed system <math>\, (\hat{A}, \hat{B}, \hat{C}, \hat{D})</math> has matrices in the following form:

: <math>\, \hat{A} = \begin{bmatrix}A_{r\overline{o}} & A_{12} & A_{13} & A_{14} \\
0 & A_{ro} & 0 & A_{24} \\
0 & 0 & A_{\overline{ro}} & A_{34}\\
0 & 0 & 0 & A_{\overline{r}o}\end{bmatrix}</math>

: <math>\, \hat{B} = \begin{bmatrix}B_{r\overline{o}} \\ B_{ro} \\ 0 \\ 0\end{bmatrix}</math>

: <math>\, \hat{C} = \begin{bmatrix}0 & C_{ro} & 0 & C_{\overline{r}o}\end{bmatrix}</math>

: <math>\, \hat{D} = D</math>

This leads to the conclusion that
* The subsystem <math>\, (A_{ro}, B_{ro}, C_{ro}, D)</math> is both reachable and observable.
* The subsystem <math>\, \left(\begin{bmatrix}A_{r\overline{o}} & A_{12}\\ 0 & A_{ro}\end{bmatrix},\begin{bmatrix}B_{r\overline{o}} \\ B_{ro}\end{bmatrix},\begin{bmatrix}0 & C_{ro}\end{bmatrix}, D\right)</math> is reachable.
* The subsystem <math>\, \left(\begin{bmatrix}A_{ro} & A_{24}\\ 0 & A_{\overline{r}o}\end{bmatrix},\begin{bmatrix}B_{ro} \\ 0 \end{bmatrix},\begin{bmatrix}C_{ro} & C_{\overline{r}o}\end{bmatrix}, D\right)</math> is observable.

==See also==
* [[Observability]]
* [[Controllability]]

==External links==
*[http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-241j-dynamic-systems-and-control-spring-2011/readings/MIT6_241JS11_chap25.pdf Lectures on Dynamic Systems and Control, Lecture 25] - Mohammed Dahleh, Munther Dahleh, George Verghese — MIT OpenCourseWare

[[Category:Control theory]]

DES-X

2013-11-23T12:52:36Z

174.52.255.118: Explicit reference to distinguish DES-X as being a symmetric-key cipher

{{Refimprove|date=August 2009}}
:''This page gives a general overview of the concept of non-measurable sets. For a precise definition of measure, see [[Measure (mathematics)]]. For various constructions of non-measurable sets, see [[Vitali set]], [[Hausdorff paradox]], and [[Banach–Tarski paradox]]''.

In [[mathematics]], a '''non-measurable set''' is a [[Set (mathematics)|set]] which cannot be assigned a meaningful "size". The [[mathematical existence]] of such sets is construed to shed light on the notions of [[length]], [[area]] and [[volume]] in formal set theory.

The notion of a non-measurable set has been a source of great controversy since its introduction. Historically, this led [[Émile Borel|Borel]] and [[Kolmogorov]] to formulate probability theory on sets which are constrained to be measurable. The measurable sets on the line are iterated countable unions and intersections of intervals (called [[Borel set]]s) plus-minus [[null set]]s. These sets are rich enough to include every conceivable definition of a set that arises in standard mathematics, but they require a lot of formalism to prove that sets are measurable.

In 1970, [[Robert M. Solovay|Solovay]] constructed [[Solovay's model]], which shows that it is consistent with standard set theory, excluding uncountable choice, that all subsets of the reals are measurable.

== Historical constructions ==

The first indication that there might be a problem in defining length for an arbitrary set came from [[Vitali set|Vitali's theorem]].{{Citation needed|date=June 2008}}

When you form the union of two disjoint sets, one would expect the measure of the result to be the sum of the measure of the two sets. A measure with this natural property is called ''finitely additive''. While a finitely additive measure is sufficient for most intuition of area, and is analogous to [[Riemann integration]], it is considered insufficient for [[probability]], because conventional modern treatments of sequences of events or random variables demand [[countable additivity]].

In this respect, the plane is similar to the line; there is a finitely additive measure, extending Lebesgue measure, which is invariant under all [[isometries]]. When you increase in [[dimension]] the picture gets worse. The [[Hausdorff paradox]] and [[Banach–Tarski paradox]] show that you can take a three dimensional [[ball (mathematics)|ball]] of radius 1, dissect it into 5 parts, move and rotate the parts and get two balls of radius 1. Obviously this construction has no meaning in the physical world. In 1989, [[A. K. Dewdney]] published a letter from his friend Arlo Lipof in the Computer Recreations column of the ''[[Scientific American]]'' where he describes an underground operation "in a South American country" of doubling gold balls using the [[Banach–Tarski paradox]].<ref>Dewdney (1989)</ref> Naturally, this was in the April issue, and "Arlo Lipof" is an [[anagram]] of "[[April Fools' Day|April Fool]]".
==Example==

Consider the unit circle ''S'', and the [[Group_action|action]] on ''S'' by a group ''G'' consisting of all rational rotations. Namely, these are rotations by angles which are rational multiples of π. Here ''G'' is countable (more specifically, ''G'' is isomorphic to <math>\mathbb{Q}/\mathbb{Z}</math>) while ''S'' is uncountable. Hence ''S'' breaks up into uncountably many orbits under ''G''. Using the [[axiom of choice]], we could pick a single point from each orbit, obtaining an uncountable subset <math>X \subset S</math> with the property that all of its translates by ''G'' are disjoint from ''X'' and from each other. The set of those translates partitions the circle into a countable collection of disjoint sets, which are all pairwise congruent (by rational rotations). The set ''X'' will be non-measurable for any rotation-invariant countably additive probability measure on ''S'': if ''X'' has zero measure, countable additivity would imply that the whole circle has zero measure. If ''X'' has positive measure, countable additivity would show that the circle has infinite measure.

== Consistent definitions of measure and probability ==

The [[Banach–Tarski paradox]] shows that there is no way to define volume in three dimensions unless one of the following four concessions is made:
# The volume of a set might change when it is rotated
# The volume of the union of two disjoint sets might be different from the sum of their volumes
# Some sets might be tagged "non-measurable" and one would need to check if a set is "measurable" before talking about its volume
# The axioms of ZFC ([[Zermelo–Fraenkel set theory]] with the axiom of Choice) might have to be altered

Standard measure theory takes the third option. One defines a family of measurable sets which is very rich, and almost any set explicitly defined in most branches of mathematics will be among this family. It is usually very easy to prove that a given specific subset of the geometric plane is measurable. The fundamental assumption is that a countably infinite sequence of disjoint sets satisfies the sum formula, a property called [[sigma additivity|σ-additivity]].

In 1970, [[Robert M. Solovay|Solovay]] demonstrated that the existence of a non-measurable set for the [[Lebesgue measure]] is not provable within the framework of Zermelo–Fraenkel set theory in the absence of the Axiom of Choice, by showing that (assuming the consistency of an [[inaccessible cardinal]]) there is a model of ZF, called [[Solovay's model]], in which [[countable choice]] holds, every set is Lebesgue measurable and in which the full axiom of choice fails.

The Axiom of Choice is equivalent to a fundamental result of [[point-set topology]], [[Tychonoff's theorem]], and also to the conjunction of two fundamental results of functional analysis, the [[Banach–Alaoglu theorem]] and the [[Krein–Milman theorem]]. It also affects the study of infinite groups to a large extent, as well as ring and order theory (see [[Boolean prime ideal theorem]]). However the axioms of [[determinacy]] and [[dependent choice]], together, are sufficient for most [[geometric measure theory]], [[potential theory]], [[Fourier series]] and [[Fourier transforms]], while making all subsets of the real line Lebesgue measurable.

== See also ==
* [[Non-Borel set]]

==References==
===Notes===
{{reflist}}
===Bibliography===
{{refbegin}}
*{{cite journal|last=Dewdney|first=A. K.|date=1989|title=A matter fabricator provides matter for thought|journal=Scientific American|issue=April|pages=116–119}}
{{refend}}

{{DEFAULTSORT:Non-Measurable Set}}
[[Category:Measure theory]]

formulasearchengine - User contributions [en]

Threefish

DES-X