Dear Joseph, some remarks from my personal experience. If the value of the determinat (D) of the matrix is zero you cannot inverse it, in principle. In this case, you have to find the linear-independent set of the eigen-vectors in order to receive the independent rank and D will not be equal to zero. If you'll choose the orthnomal basis of the eigen-vectors you can transfrom your matrix in the triangle form.  

Hi, if you compute an eigenvalue decomposition of M you will obtain something of the following form:

M = Q*L*inv(Q)

where L is diagonal and contains the eigenvalues of M and Q is formed by the eigenvectors (column i of Q is the eigenvector number i).

As M is snigular some eigenvalues will be equal to zero.

Thus, M + k*I = Q*(L+k*I*)*inv(Q)

and the inverse can be written as:

inv(M) = Q*inv(L+k*I)*inv(Q)

I would use identity A^-1=adj(A)/det(A) and Sylvester's determinant identity  because matrix  M can be expresed as M=v.vT ,where v is a column vector (1,1,1....1)T.  Using the identity one gets det(Mnxn +k*Inxn)=kndet(I+1/k*v.vT)=kn(1+n/k).

Due to the symmetry of the matrix, the diagonal elements of the adjugate matrix are adj(A)ii=det(Mn-1xn-1 +k*In-1xn-1)=kn-1(1+(n-1)/k).

The nondiagonal elements adj(A)ij can be solved similarly again using the Sylvesters identity, however one must create invertible matrix from one column of the submatrix of M and submatrix of k*I and adjust the vectors for experssing the matrix M with missing column as a tensor product. The result is adj(A)ij=-kn-2

In summery the diagonal elements of the inversion are 

(Mnxn +k*Inxn)-1ii=(n-1+k)/(n*k+k^2)

and non-diagonal are (i not equal to j)

(Mnxn +k*Inxn)-1ij=-1/(n*k+k^2)

Dear colleagues

Thank you very much for your very useful answers.

Regards, Joseph

Dear Peter Breuer,

Your answer is very nice but in my case k

Dear Jiří Falta,

Your solution is beatiful!  Computer simulation showed that it is correct.

Regards,

Joseph

Dear Joseph, for your example, and for k=-1, you can apply the group inverse, see Markhov chains and group inverse, I am sure you will find a good solution.

In general, If M singular that doesn't mean M+KI is singular, it can be invertible, especially if M diagonal with 1 on the diagonal and k not equal -1, the inverse in this case is very easy, just invert the diagonal elements.

If M is not diagonal, I think the best method is to take canonical Jordan form and use either the exponential of the matrix in that form or the expansion of the function 1/X 

Dear Hanifa, very interesting idea!

Dear All,

Use the well-known fact (LaTeX code): $(I+\frac{1}{k}cc^{T})^{-1}=I-\frac{1}{k+\|c\|^{2}}cc^{T}$. In particular one may have: $c^{T}=\left [\begin{array}{cccc} 1 & 1 & \cdots & 1\end{array} \right ]$. Recall that eigenvaules of the first matrix are: either $1$ or $\frac{k+\|c\|^{2}}{k}$ ($c$ is a corresponding eigenvector); $k\neq 0$, $k\neq -\|c\|^{2}$.

20 years ago, I discovered an algorithm that pseudo-inverts any matrix, by constructing it recursively. See the file in attach.

Dear prof Manuel Duarte Ortigueira 

Very useful answer and very interesting article!

Regards, Joseph Dubrovkin

 Dear Peter Breuer,

You are absolutely right that we're speaking different languages. It is  difficult for me

to understand  different ideas and short mathematical exercises of professionals. Therefore in some cases I cannot respond  quickly and I must check all materials. I do not need general solutions therefore the simplest solution of the partial case was very useful for me in the first stage of my study.  

I appreciate your original  literary passage about the Wall of China and the Mechanical Turk.

 Regards,

Joseph Dubrovkin

Dear Peter Breuer!

I formulate my goal  in attached file. I need only analytical solution (if any).

Thank you very much for your attention!

Regards,

Joseph 

Please look at Moore-Penrose matrix inverse. Basically for a singular matrix B you find matrix A such that

ABA=A, BAB=B

Hi Joseph. There is an algoritm inverting a concatenated matrix B=[A I], called sometimes Chio's method. This is nothing else, but rref(B) that gives [I A'] even for ill-conditioned A. Do you need the invert of M(n x n) + kI(n x n) be represented also as a sum? 

@ Joseph Dubrovkin

Thanks for much more clear setting of your problem. It is still unclear  what is the source of singularity. In fact, if  the sequence of \eta-s is arithmetic , then for at least three columns we have:    Col_{j+1}  - 2 Col_{j+2} + Col_{j+3} is the column of zeros (see the PS below), for every possible  j , thus  practically the assumption of singularity is superfluos. If, in turn, the sequence comes from sampling the gaussian function, then every subdeterminant is stricly positive for distinct points where the value of the function are taken as  \eta-s (which follows from general theorems on totally positive kernels, elaborated systematically as an extension of Chebyshev systems by Samuel Karlin in early seventhies). Due to Sylvester's formulas, this is then due to M. Thus it is hard to get singularity in this particular case. Therefore an interesting question appears: WHY do you assume singularity at all? [vide other answers in this post].  However this is not merital. Once you want to assume this, so let it be.

Next, more important question: having the  form of  M, how one can find the eigenvalues. Some nice feature is, that the matrix  M  is  a covariance matrix, i.e. it is real, symmetric and weakly positive definite. Hence, all eigenvalues are  real and non-negative. Moreover all eigenvectors are real and can be chosen as full orthonormal system. And therefore also,  in your question the forbidden values of k are only those, which are elements of the spectrum. And you can apply the algorithm by Richard Epenoy, who has suggested very correcly for this case, to reduce by application of the column of eigenvectors the problem to the inverse  

[Diag(spectrum - k)]^{-1} =  Diag( (spectrum - k)^{-1} ).

Then however the decomposition 

  M= [EeigenVectors}^{-1} [Diag(spectrum - k)] [EeigenVectors}

becomes crucial. The only advantage is, that choosing an orthonormal sytem of eigenvector, the inverse equals the transposed matrix.

Perhaps, the remarks by Daniil Yurchenko or by Peter Breuer  can help in simplifying the algorithm of digonalization. Am I right?

Best regards to all followers

PS.  If \etas form arithmetic sequence (the case of linear function sampled at equisistant points), then additional advantage appears due to the equality used already above, that  allows to solve the problem for matrices  \Eta that their transposed columns possess the form of

[Col_j]^T  = [0,2,3,. . . , L-N]   +   ( j + a) \cdot [1,1,1,..., 1],  for all  j = 1,2, . . ., N.

for some   a  , obviously, unless the function is constant :)

JD

@JOSEPH

Give matrices of your actual problem in short dimension (4x4) . I  hope to give the inverse of it . First take the sum then inverse . More ever spell the  the one ,which will

be of actual use .

B.Rath

@Biswanath Rath

See linear case in attached file. I want analytical solution of the linear case, if any.

I will cited you in my future article for your assistance.

Thank you very much.

Regards, Joseph 

Dear ALL!

I need time to "digest" your answers!

Thank you very much,

Regards, Joseph

@Joseph

Please spell out correctly . Do you want 

AA * FF + k eye(5) = B 

Find  inv(B)

With  k =0.01 

Waiting your reply,  Further if you want other values 

inform the same . You can take any value of k.If you want 

EIGENVALUES OF 'B 'or INV(B)  mention the same.Reply early

Prof B.Rath

@Biswanath Rath

I want inv(B) in analytical form not eigenvalues. I have numerical solution in MATLAB.

B=FF'*FF+ k eye(5) where FF is [ 1 2 3 4 5; 2 3 4 5 6; and so on]

k is small 0.001,  0.0001 ...  

Thank you very much.

@JOSEPH

• More than (3×3) is difficult for analytical calculation. For order (5×5) I can calculate numerically . If you want , I will do that . Further spell out the meaning of FF' .
• Prof Rath

@Joseph, I am still not sure - do you want a close-form of the inverse as a function of k? If yes, see enclosed results for FF7x5 and FF7x4. It is computed with WolframAlpha. 

@ Joseph Dubrovkin, Viera Cernanowa

The attached file is a draft version of an algorithm which in final number of steps allows to use an algebraic formula for the inverse matrices in the linear case. Itwould be interesting if it is consistent with your  calculations. The possibility of obtaining the formula is stricly related to the linearity of the source function.

PS. It is still not clear, why the assumption of the singularity of  M is so important!?

PS2 The enclosed version has corrected two misprints, which appeared (themselves:) in the former article.

Best regards

@Joachim Domsta,  Viera Cernanowa

Tomorrow I will study your solutions.

Thank you very much

@Joachim, could you please include an example, apply your algorithm? Thanks.

@Joachim Domsta

First question is in attached file.

Thank you very much! Very interesting solution.

@ Joseph Dubrovkin

1.1.  the vector  $U$ is of constant terms equal \sqrt{N}^{-1)   ( not  \sqrt{N} )

1.2.  V is defined correctly

1.3. K^{(2)}  is defined as a sum with  k running from  1  to  N (not to L-N+1)

Thanks for the discovery!

@ Viera Cernanowa

Actually I feel  a little bit exhausted, Hopefully I have another weekend for preparing a detailed example:) :( 

Regards

@Joachim Domsta

I check your interesting solution by MATLAB simulation (see attached file).

There is a little correction K0= K0-1 in some expressions.

But in the final results we need a correction matrix. Maybe you can find an error?

Thank you very much.

Joseph

@Joseph

Thanks for your trial; I am not using any calculating programm/package, so I cannot verify precisely your code. However I shall chech everything ones more. I an surprised by the correction  of  k_0 about 1.  I need a weekend for this. The first version of the algorithm is a rather complete skech, but just a sketch. For final form some excercises are needed. Yor test will help me certainly. Thanks again.

@ All Followers

There is question, whether the small terms should be neglected. I say no, unless the problem is to find (what has been mentioned by some other participants) the limit of  k \cdot (M + k \cdot I){-1} as k \to 0.

Regards

@Joachim Domsta

My program is correct. Maybe there is a small error in your derivation?

Thank you very much.

@ Joseph Dubrovkin

I couldn't resist in checking at least a little your last file.

I heve noticed, that the correction equals 

 [  - 1.5 \cdot  U \circ U'  + 0.5 V \circ  V' ] / z

It cannot be incidental. Therefore, please send me also in a doc file

the  5by5 matrices  inv(M+z I)  and  invMzTheor .

Thanks in advance,

Joachim

Sorry, I was wrong claiming that the correction term equals 

 [  - 1.5 \cdot  U \circ U'  + 0.5 V \circ  V' ] / z

Despite this, my request for the matrices is still ON :)

Best, JD

@ Joseph

The following is the main part of  $10 \cdot  invMzTheor$ for  $ N=5 $ evaluated according to my formula:

 4    -4    -2    0     2

-4     7    -2   -1     0

-2    -2     8   -2    -2

 0    -1    -2    7    -4

 2     0    -2    -4    4

Let me be forgiven, that without your detailed result I am trying to guess, that row  V'  by  you applied to my formula was    

[ -3  -2  -1   0   1  ] / \sqrt{10}    instead  of   [ -2 -1 0 1 2 ] / \sqrt{10}

[ or something similar ] .  Wasn't it ?

Very interested, JD

I still have not enough time for finding  ventual error(s) in my solution. Can someone make this for me, please?  My answer for the case of  N=5 gives for the limit  of the inverse function as  z \to 0 (independently of  any fixed L \ge N):

LIMIT(5) := \lim z \cdot (M+z\cdot I)^{-1} =

                           4    -4    -2    0     2

                          -4     7    -2   -1     0

1/10 \cdot \left[   -2    -2     8   -2    -2  \right] 

                            0    -1    -2    7    -4

                            2     0    -2    -4    4

(semi-LaTeX coding applied:). This is the result of application of the following formulas:

LIMIT(N) = I -  U \circ U'  -  V \circ V'   as    z \to 0

U' = 1/ \sqrt{N} [ 1, 1, 1, . . . 1, 1 ] \in  \R^N

V' =  1/\sqrt{K^{(2)} }} [ -(N-1)/2 ,  -(N-1)/2 +1, -(N-1)/2 +2, . . ., (N-1)/2 ]

K^{(2)} = ( -(N-1)/2 )^2 + ( -(N-1)/2 +1 )^2 + ( -(N-1)/2 +2 )^2 , . . . , ( (N-1)/2 )^2 .

Remark.  Obviously, then  U  and  V  form an orthonormal pair.

The questions are:

-- is LIMIT(5)  consistent with direct calculations by Joseph  for  N=5, L=13?

-- Is this consistent with my presentation of the solution within answer no. 30 few days ago?

Thanks in advance,

Joachim

Dear Viera,

Finally, I have compared  your solution (post no. 29) with LIMIT(N) for both N=5  and  N=4. They agree!  Congratulations go to both of us! However I am still not enough patient for comparing other details. Hopefully, the example of application of my algorithm, which have been kindly asked by you  will be elaboreted in few days. But this is not a promise, only a hope:)

Best regards, Joachim

PS.  "my" theoretical LIMIT(4) equals as follows, where the second  term is   U\circ U'   and the third is   V \circ V'  the orthonormal pair is formed by

      U' = [0.5 0.5 0.5 0.5],      V' = [ -3  -1   1  3] / \sqrt{20}

:

1  0  0  0           0.25  0.25  0.25  0.25            0.45  0.15  -0.15   -0.45

0  1  0  0     -     0.25  0.25  0.25  0.25      -     0.15   0.05  -0.05  -0.15 

0  0  1  0           0.25  0.25  0.25  0.25            -0.15  -0.05  0.05   0.15

0  0  0  1           0.25  0.25  0.25  0.25            -0.45  -0.15  0.15   0.45

         0.3    -0.4    -0.1    0.2

=      -0.4     0.7    -0.2   -0.1

        -0.1    -0,2     0.7   -0.4

        0.2     -0.1    -0.4    0.3

( LIMIT(5)  is given within the answer no. 41 )  JD

can you tell me some new properties of the polynomials of Bernoulli and Euler

thanks

@ Messahel Abdelkader

Dear sir,

Seemigly the subject of your interesting question is rather far away from the discussed here invertibility of matrices.Let me suggest to post it a a separate problem.

Best regards

PS. It is really very interesting what is NEW about Bernouli and/or Euler polynomials!

@ Joachim Domsta

Dear Joachim Domsta

I apologize for the delayed response because entangled in continuing discussions.

Regards, Joseph

Dear Joseph Dubrovkin,

You have two errors which at the beginning cancel each other:

correct is the following     eta0 = j0 + k0 -1,      V' =  [ k - k0:  k=1,2,. . .,N]

wrong is the following:      eta0 = j0 + k0,          V' = [ k - k0 - 1: k=1,2,...,N]

Regards, Joachim

Dear Joachim Domsta.

I  am very pleased to inform you that your decision coincides with the numerical calculation.

I will cite that it is your formula in my future article.

Thank you very much.

Regards, Joseph

Dear Joseph Dubrovkin,

Thanks for your thanks. And this sufficies. The method is well known from the functional analysis of Hilbert spaces, and is adopted even to probability transitien matrices e.g. in works by  Turbin and Korolyuk. Please, however, don't ask me for detailed references; they can be found in many places. In a slightly more general setting, the the problem posed by you relates to operators, say  T  on a direct sum of two linear spaces, say X\oplus Y  into  the same space,  whose action equals  as follow  T(x+y) =  T_o(y), where   T_o is an isomorphism of  Y. My contribution is, that I have noticed, that the special case of arithmetic sequence  \eta_j allows such a presentation of the matrix M.

Unfortunately, this will not work for other functions like, e.g. quadratic, the more for exponential functions, like gaussian. Thus I can agree if you publicate my suggestion about the emphasized fact at most.

Best wishes, Joachim Domsta

Dear Joseph,

it seems to me that the problem is similar to discretization of a Fredholm integral equation with the kernel given by K(x,y)=1/delta*\int_0^\delta \eta(x+s) \eta(y+s) ds. (see the attachment) You may consider calculating the kernel analyticaly for some functions (polynomials, Gaussian) and discretizing it afterwards. At least for polynomials the integration leads to a degenerate kernel. In such a case the inverse can be found quite easily, see the first link, page 27.

In the discretized case the method leads to a Woodbury Formula(second link), which is generalization of the formula mentioned by Piotr Grabowski.

Best regards

Jiri

http://www2.kau.se/yourshes/integrkomp.pdf

http://mathworld.wolfram.com/WoodburyFormula.html

Dear Jiří!

Thank you very much for your nice answer.

Regards, Joseph

Dear  Joachim Domsta!

I found that your term can not be neglected in correct calculations

R_z (1,1)UU^T+R_z (1,2)(UV^T+VU^T )+R_z (2,2)VV^T

despite the "same" inverse matrix since "invisible" small computational errors of this matrix have strong impact on the results. 

I express to you my most sincere assessment of your brilliant solution!

Joseph

Joseph,  Thank for your kind thanks,

I wish a lot of successes  in Research within This Gate:)

Joachim