A Critical Study on Idempotent Matrices and Its Significance

Looking up some customer's name and address in a database are typically idempotent (in fact nullipotent), since this will not cause the database to change. Similarly, changing a customer's address is typically idempotent, because the final address will be the same no matter how many times it is submitted. However, placing an order for a car for the customer is typically not idempotent, since running the method/call several times will lead to several orders being placed. Canceling an order is idempotent, because the order remains canceled no matter how many requests are made. A composition of idempotent methods or subroutines, however, is not necessarily idempotent if a later method in the sequence changes a value that an earlier method depends on – idempotence is not closed under composition. For example, suppose the initial value of a variable is 3 and there is a sequence that reads the variable, then changes it to 5, and then reads it again. Each step in the sequence is idempotent: both steps reading the variable have no side effects and changing a variable to 5 will always have the same effect no matter how many times it is executed. Nonetheless, executing the entire sequence once produces the output (3, 5), but executing it a second time produces the output (5, 5), so the sequence is not idempotent. In the HyperText Transfer Protocol (HTTP), idempotence and safety are the major attributes that separate HTTP verbs. Of the major HTTP verbs, GET, PUT, and DELETE are idempotent (if implemented according to the standard), but POST is not. These verbs represent very abstract operations in computer science: GET retrieves a resource; PUT stores content at a resource; and DELETE eliminates a resource. As in the example above, reading data usually has no side effects, so it is idempotent (in fact nullipotent). Storing a given set of content is usually idempotent, as the final value stored remains the same after each execution. And deleting something is generally idempotent, as the end result is always the absence of the thing deleted. In Event Stream Processing, idempotence refers to the ability of a system to produce the same outcome, even if an event or message is received more than once. In a load-store architecture, instructions that might possibly cause a page fault are idempotent. So if a page fault occurs, the OS can load the page from disk and then simply re-execute the faulted instruction. In a processor where such instructions are not idempotent, dealing with page faults is much more complex. Idempotent matrices arise frequently in regression analysis and econometrics. For example, in ordinary least squares, the regression problem is to choose a vector of coefficient estimates so as to minimize the sum of squared residuals (mispredictions) ei: in matrix form, where y is a vector of dependent variable observations, and X is a matrix each of whose columns is a column of observations on one of the independent variables. The resulting estimator is where superscript T indicates a transpose, and the vector of residuals is[2] Here both M and (the latter being known as the hat matrix) are idempotent and symmetric matrices, a fact which allows simplification when the sum of squared residuals is computed: variance of the estimator . An idempotent linear operator P is a projection operator on the range space R(P) along its null space N(P). P is an orthogonal projection operator if and only if it is idempotent and symmetric. As mentioned above, the identity map and the constant maps are always idempotent maps. The absolute value function of a real or complex argument, and the floor function of a real argument are idempotent. The function that assigns to every subset

idempotent on the power set of . It is an example of a closure operator; all closure operators are idempotent functions. The operation of subtracting the average of a list of numbers from every number in the list is idempotent. For example, consider the numbers . The average Is . Subtracting 7 from every number in the list yields . The average of that list is . Subtracting 0 from every number in that list yields the same list.

The Kleene star and Kleene plus operators used to express repetition in formal languages are idempotent.

An idempotent element of a ring is, by definition, an element that is idempotent for the ring's multiplication. That is, an element a is idempotent precisely when a2 = a. Idempotent elements of rings yield direct decompositions of modules, and play a role in describing other homological properties of the ring. While "idempotent" usually refers to the multiplication operation of a ring, there are rings in which both operations are idempotent: Boolean algebras are such an example.

In Boolean algebra, both the logical and and the logical or operations are idempotent. This implies that every element of Boolean algebra is idempotent with respect to both of these operations. Specifically, and for all . In linear algebra, projections are idempotent. In fact, the projections of a vector space are exactly the idempotent elements of the ring of linear transformations of the vector space. After fixing a idempotent semiring (also sometimes called a dioid) is a semiring whose addition (not multiplication) is idempotent. If both operations of the semiring are idempotent, then the semiring is called doubly idempotent.

In computer science, the term idempotent is used more comprehensively to describe an operation that will produce the same results if executed once or multiple times. This may have a different meaning depending on the context in which it is applied. In the case of methods or subroutine calls with side effects, for instance, it means that the modified state remains the same after the first call. In functional programming, though, an idempotent function is one that has the property f(f(x)) = f(x) for any value x. This is a very useful property in many situations, as it means that an operation can be repeated or retried as often as necessary without causing unintended effects. With non-idempotent operations, the algorithm may have to keep track of whether the operation was already performed or not.

A unary operation , that is, a map from some set into itself, is called idempotent if, for all in , In particular, the identity function , defined by , is idempotent, as is the constant function , where is an element of , defined by . An important class of idempotent functions is given by projections in a vector space. An example of a projection is the function defined by , which projects an arbitrary point in 3D space to a point on the -plane, where the third coordinate () is equal to 0. A unary operation is idempotent if it maps each element of to a fixed point of . We can partition a set with elements into chosen fixed points and non-fixed points, and then is the number of different idempotent functions. Hence, taking into account all possible partitions, is the total number of possible idempotent functions on the set. The integer sequence of the number of idempotent functions as given by the sum above for starts with

Neither the property of being idempotent nor that of being not is preserved under composition of unary functions. As an example for the former, f(x) = x mod 3 and g(x) = max(x,5) are both idempotent, but f∘g is not, although g∘f happens to be. As an example for the latter, the negation function ¬ on truth values isn't idempotent, but ¬∘¬ is.

Given a binary operation on a set , an element is said to be idempotent (with respect to ) if: . In particular an identity element of , if it exists, is idempotent with respect to the operation . The binary operation itself is called idempotent if every element of is idempotent. That is, for all when denotes set membership: . For example, the operations of set union and set intersection are both idempotent, as are logical conjunction and logical disjunction, and, in general, the meet and join operations of a lattice.

The connections between the three notions are as follows.

• The statement that the binary operation ★ on a set S is idempotent, is equivalent to the statement that every element of S is

idempotent for ★.

• The defining property of unary idempotence, f(f(x)) = f(x) for x in the domain of f, can equivalently be rewritten as f ∘ f = f, using the binary operation of function composition denoted by ∘. Thus, the statement that f is an idempotent unary operation on S is equivalent to the statement that f is an idempotent element with respect to the function composition operation ∘ on functions from S to S.

absolute value function of a real or complex argument, and the floor function of a real argument are idempotent. The function that assigns to every subset

idempotent on the power set of . It is an example of a closure operator; all closure operators are idempotent functions. The operation of subtracting the average of a list of numbers from every number in the list is idempotent. For example, consider the numbers . The average is . Subtracting 7 from every number in the list yields . The average of that list is . Subtracting 0 from every number in that list yields the same list.

The Kleene star and Kleene plus operators used to express repetition in formal languages are idempotent.

An idempotent element of a ring is, by definition, an element that is idempotent for the ring's multiplication. That is, an element a is idempotent precisely when a2 = a. Idempotent elements of rings yield direct decompositions of modules, and play a role in describing other homological properties of the ring. While "idempotent" usually refers to the multiplication operation of a ring, there are rings in which both operations are idempotent: Boolean algebras are such an example.

1. Polcino & Sehgal (2002), p. 127. 2. If f and g commute, i.e. if f∘g = g∘f, then idempotency of both f and g implies that of f∘g, since f∘g ∘ f∘g = f∘f ∘ g∘g = f ∘ g, using the associativity of composition. 3. e.g. f(g(7)) = f(7) = 1, but f(g(1)) = f(5) = 2 ≠ 1 4. also showing that commutation of f and g is not a necessary condition for idempotency preservation 5. See Hazewinkel et al. (2004), p. 2.