Questions on the various algorithms used in linear algebra computations (matrix computations).

learn more… | top users | synonyms

0
votes
0answers
33 views

How to generate random matrices when it's singular values are given?

Consider matrix S as nxn diagonal matrix with singular values populated across the diagonals in non-increasing order. I want to know how to create random matrix A whose singular values with be the ...
1
vote
0answers
56 views

How to condense a matrix to a vector

I'm not an experienced person in mathematics and this might either sound like a trivial question or a stupid one. However, this problem arose to me when I was writing a program. Following is my ...
3
votes
1answer
56 views

Proving an identity

We define $\|x\|_A^2:= x^TAx$ and $(x,y)_M := y^TMx$ for a symmetric positive definite matrix $A$ and an invertible matrix $M$. I want to show the following identity for the errors of Richardson's ...
2
votes
0answers
93 views

How to generate a random matrix which have given singular values?

I know one method: generate a random matrix, apply SVD decomposition, modify singular values, and then multiply those matrices back together. However, I'm wondering how random this method is. Since ...
2
votes
1answer
77 views

Characterizing a matrix with identical eigenvalues

Suppose $n \times n$ hermitian and positive semi-definite matrix $A$ is given. We can rewrite $A$ using its eigen decomposition, $$ A = U_A \Lambda_A U_A^H. $$ Now suppose matrix $B$ is also $n ...
1
vote
1answer
102 views

Preservation of Positive-Definiteness from Small Perturbations

Let $A$ with real positive entries be a Hermitian positive definite matrix. I'm wondering if one perturbs $A$, e.g., $\hat{A}=A+\Delta A$, would the matrix still be positive definite? I'm told this is ...
3
votes
1answer
258 views

What are non-orthogonal eigenvectors?

Given a symmetric matrix $A$, the maximum of the trace, $Tr(Z^TAZ)$ under the assumption that $Z^TZ=I$ occurs when $Z$ has the eigenvectors of $A$, as $Tr(U^TAU)= \lambda_1 +\lambda_2+...\lambda_ d$ ...
0
votes
1answer
36 views

Constrained non-linear optimisation algorithm making use of problem structure

I have a problem that in some ways is quite simple and in other ways is quite hard. I feel that there is probably an algorithm out there that is better suited to solving my problem than the one I am ...
0
votes
0answers
113 views

Symmetric Tridiagonal QR Algorithm

I have a question regarding QR algorithm. Suppose we are being given a symmetric tridiagonal matrix A (4X4) and perform QR factorization on A: A=QR. Then we define A':=RQ. A' still possesses the ...
1
vote
0answers
57 views

Reformulating objective function of canonical correlation analysis

Given two column vectors $X = (x_1, \dots, x_n)'$ and $Y = (y_1, \dots, y_m)'$ of random variables with finite second moments, canonical-correlation analysis seeks vectors $a$ and $b$ such that the ...
0
votes
1answer
55 views

Need Help! Recognizing types of errors: Truncation and Roundoff

I am a little unclear on the difference between the two. What exactly are they? As simplified as possible :) How can i recognize them and identify parts of formulas or algorithms that would give ...
2
votes
1answer
238 views

Why is the matrix norm $||A||_1$ maximum absolute column sum of the matrix.

By definition, we have: $||V||_p=\sqrt[p]{\displaystyle \sum_{i=1}^{n}|v_i|^p}$ $||A||_p=sup\frac{||Ax||_p}{||x||_p}$, $x\not=0$ and if $A$ is finite, we change sup to max. However I don't really ...
0
votes
1answer
48 views

how to find thet a given real symmetric matrix is positive definite, positive semidefinite, negative definite, negative semidefinite or indefinite.

How to find that a given real symmetric matrix is positive definite, positive semidefinite, negative definite, negative semidefinite or indefinite.; on the basis of principle diagonal minor.
0
votes
2answers
20 views

if $v$ is a member of $H$ and $v$ is not a member of $M$ then $u$ is member of $K$. How is this possible?

Let $(V,K)$ and $u,v$ is a member of $V$. Suppose that $M$ is a subset of $V$ is a subspace of $V$ with basis $B_m=\{m_1,...,m_r\}$ with $r$ less than and equal to $n$. Let $H$ be a subspace spanned ...
0
votes
1answer
80 views

Singular value decomposition: rotation

Suppose that $A \in \mathbb{C}^{m \times n}$ and $B$ ($ \in \mathbb{C}^{n \times m}$) is the matrix obtained by rotating $A$ ninety degrees clockwise. Do $A$ and $B$ have the same singular values? ...
1
vote
1answer
3k views

Distance/Similarity between two matrices

I'm in the process of writing an application which identifies the closest matrix from a set of square matrices $M$ to a given square matrix $A$. The closest can be defined as the most similar. I ...
1
vote
0answers
40 views

Matrix computing

Given an $n$-vector $x$, show that floating-point computation of the Householder vector $v$ such that $P x = (I − 2vv^{T} )x = \pm\left\|x\right\|_{2}e_{1} $ gives a forward stable result $v^{\prime}$ ...
0
votes
1answer
37 views

quick factorization of rank-one matrices (generally, and of a particular form)

Let $Q$ be an arbitrary non-zero matrix and let $x$ be a column vector. It should be true that $xx^TQ$ and $Qxx^T$ are both rank 1 matrices. It is a fact that all rank-one matrices can be factorized ...
1
vote
1answer
89 views

Bilinear Coons patches

Suppose that we have two bilinear Coons patches which share a common curve. Studying on Farin I find that, generally, these two surfaces join with C^0 continuity along that common curve, but I don't ...
0
votes
1answer
38 views

Time of point colliding with a moving line

In 2-D space, given a line defined by two points a and b, and a third point c that is not initially (t=0) in the line defined by a and b, is it possible to obtain an expression for the numerically ...
0
votes
2answers
811 views

Prove that the determinant of a householder matrix is -1

I understand that a householder matrix has eigenvalues of either 1 or -1, however I isn't clear to me why the determinant is -1. Clearly the determinant is equal to the product of the eigenvalues so ...
1
vote
0answers
107 views

Matrix-valued expansion in spherical harmonics

I am seeking a clever solution to the following problem. Given $$X(\theta,\phi) = exp(-iA(\theta,\phi))\; B\; exp(+iA(\theta,\phi))$$ with the square, Hermitian matrix $A$: $$A(\theta,\phi) = A_{0,0} ...
4
votes
1answer
127 views

Uniform sampling of points on a simplex

I have this problem: I'm trying to sample the relation $$ \sum_{i=1}^N x_i = 1 $$ in the domain where $x_i>0\ \forall i$. Right now I'm just extracting $N$ random numbers $u_i$ from a uniform ...
1
vote
1answer
225 views

What is the operation count for QR factorization using Householder transformations?

I have a hard time finding the operation count of QR factorization when using Householder transformations. The answer is $2mn^2 - \frac{2n^3}{3}$, but have no clue on how to get this count following ...
1
vote
3answers
81 views

How to solve this matrix using gauss-elimination by hand

I feel like i am having a brain fart. I have been given this $Ax=b$ system: $A= \begin{pmatrix} 0.913 & 0.659 \\ 0.780 & 0.563 \end{pmatrix}$ $b= \begin{pmatrix} 0.254 \\ 0.217 \end{pmatrix}$ ...
1
vote
1answer
64 views

Convergence of Recursive algorithms

In a kind of signal processing problem I faced the following recursive (boot-strap) algorithm: $$R_{k} = R_{k-1} + (y_k-H s_{k-1})*(y_k-H s_{k-1})^T$$ $$s_k = (H^T R_k^{-1} H)^{-1} H^T R_k^{-1} ...
1
vote
0answers
690 views

The spectral radius of the matrix $A$ is less than or equal any natural norm

Show that the spectral radius of the matrix A is less than or equal any natural norm, i.e: $$\rho(A) \leq ||A||=\max_{||x||=1}{||Ax||}$$ where $\rho(A)=\max\{|\lambda|:\lambda \text{ is a eigenvalue ...
1
vote
1answer
170 views

1D Schrodinger/Laplace equation via finite differences: incompatible eigenvalues

I need to solve a variant of the 1D Schrodinger's equation equation using finite differences, so I decided to play a little bit with the real-space representation of some operators. Using the ...
0
votes
0answers
18 views

Complexity of the Product of 2 Orthonormal Matrices

I have two $n \times n$ matrices $A$ and $B$ which are both orthonormal and would like to calculate the product $A^TB$. Is there a way to exploit the orthonormal nature of the matrices to calculate ...
1
vote
2answers
128 views

Is there a compelling reason for the $lcd$ per se and $lcd\equiv lcm$ in fraction arithmetics?

I haven't done arithmetics during the past few years, so I'm filling the gaps before I'm starting out in math in a month, so I have little understanding of the numerics. I've come across such a gap ...
1
vote
1answer
68 views

Iteration to find squre root of positive semidefinite matrix

Suppose matrix $A$ is positive semidefinite and $I\succeq A$. Prove that the iteration $$Y_0=0,\hspace{3mm} Y_{n+1}=\frac{1}{2}(A+Y_n^2)$$ is nondecreasing (that is, $Y_{n+1}\succeq Y_n$ for all ...
0
votes
1answer
40 views

In linear iteration, find values for a,b that cause different outcomes

When iterating the equation $X_n=AX_0 + B$ for some initial value $X_0$, I need to find concrete values for $A$ and $B$ that: 1) cause the series to converge for some initial value $X_0$ and diverge ...
1
vote
1answer
156 views

How do deal with a giant sparse matrices?

Someone point me in the right direction. I'm looking to do some heavy-duty manipulation of some really large and often very sparse matrices. Naturally, this problem overlaps programming heavily (I ...
1
vote
1answer
149 views

Ideas on matrix factorizations and/or transformations for $\ell_1$ minimization

I am starting with a typical $\ell_1$ basis pursuit problem: $$ \min_{\mathbf{x}} \Vert \mathbf{x} \Vert_1 \quad \mathrm{s.t.} \quad \Vert \mathbf{ERx} - \mathbf{y} \Vert_2 \leq \epsilon, $$ where ...
1
vote
2answers
169 views

Area formula for $n$-gon

Is there a formula for the area of a general polytope with $n$ vertices which just uses the distances between vertices, like Herons formel for the area of a triangle?
2
votes
0answers
58 views

Inverses of the sums of all possible subsets of a set of symmetric and positive definite matrices

I have a set of $c$ matrices $A_1 ... A_c$ which are all symmetric and positive definite. I would like to calculate the inverses of all the possible sums, i.e. ...
1
vote
0answers
101 views

Fast way to find a matrix with only $0$ and $1$ as entries full-rank or not?

I have a huge number of small Zero-One Matrices($4\times 4$, $5\times5$,$6\times6$) and I want to determine whether they are full-rank or not one by one. Gaussian elimination is a option, I want to ...
0
votes
0answers
45 views

Counting the number of additions/subtractions for Gauss-Jordan Elimination

We have a matrix of the form $$\Big[\;\;\;n\times n\;\;\;\Big|\;\;\;n\times m\;\;\;\Big].$$ Where the set up is basically solving $m$ linear systems of equations all with the same coefficient ...
0
votes
2answers
196 views

Show a class of tridiagonal matrices is nonsingular.

I'm studying for an exam and came across a problem I can't seem to solve. The problem is as follows. Show that tridiagonal matrices ...
1
vote
0answers
462 views

Least Squares “analytic expression” for fitting a 2D quadratic function to measurements

I have n scattered elevation measurements: $ \{x_i,y_i,z_i\}_{i=1..n} $ that I want to fit a quadratic function to: $ z = ax^2 + by^2 + cxy + dx + ey + f$. The problem can be written as a vector ...
1
vote
1answer
133 views

Power iteration provably works if the matrix has a unique eigenvalue $\lambda$ and $\lambda>0$

Let $A$ be a $n\times n$ real matrix and $v_0 \in \mathbb R^n$ s.t. $||v_0|| = 1$. Define a sequence $(v_k)_k$ of $n$-dimensional real vectors by $v_k = A^kv_0 / || A^kv_0 ||$. Assume that $A$ has a ...
0
votes
3answers
87 views

Proving nonsingularity of a sum of matrices

I'm trying to solve this study question but I'm not sure how to proceed. The question is as follows. If \begin{equation}\frac{||B||_2}{||A||_2}<\frac{1}{\kappa_2(A)}\end{equation} with ...
3
votes
1answer
179 views

On minimizing matrix norm

Given $m\geq n \geq k$ and $A \in M^{m\times n}(\mathbb{C})$, the problem asks to evaluate $$\inf_{\textrm{rank}(B)\leq k}||A-B||$$ and gives condition on $A$ making the above minimum is taken by ...
2
votes
0answers
57 views

What is the significance of the matrix in the LAPACK logo?

This is the LAPACK linear algebra library logo: What is the significance of this matrix?
2
votes
1answer
149 views

What does it mean/imply that all my singular values are ones?

Suppose I apply SVD (singular value decomposition) on some real-valued matrix $M$, that is, $M = USV^T$. Now, if $S$ is an identity matrix, what does it mean? Does $M$ have some special properties? ...
1
vote
1answer
194 views

Solving commutator equation: $AX-XA=M$

Consider the field square matrices $M_n(\mathbb{C})$ or $M_n(\mathbb{R})$. I wish to solve the equation $AX-XA=M$ for a given $A,M$. Obviously this is just $n^2$ linear equations and thus is trivial ...
2
votes
2answers
58 views

Is this the correct solution?

Determine the coordinates of the vector $U=(4,5,-3)\;\text{of}\; R^3$ with respect to base ${(1,0,0), (0,1,0), (0,0, 1)}$ $$x(1,0,0) + y (0,1,0) + z (0,0,1) = (4,5, -3)$$ $$(x, 0,0) + (0, y, 0) + ...
0
votes
1answer
219 views

How do I calculate the values of the control points for an uniform cubic B spline surface?

I want to interpolate the following 3 scattered data points: (80.9,58.5,48.0),(35.0,89.6,82.3),(74.7,17.4,85.9) by an uniform cubic B spline surface on the following control lattice, $ \phi $: In ...
0
votes
1answer
85 views

matrix positive semidefinite

If $n \times n $ matrices $A, B$ are positive semi-definite, matrices $P$ and $Q$ are $n\times p$ and $n\times q$ matrices and their column vectors are orthogonal, which is to say $$P^{T}P=I_{p\times ...
0
votes
1answer
231 views

approximating diagonal of inverse sum of low rank and diagonal matrices

I was wondering if there is any theorem or algorithm to approximate the diagonal elements of the inverse of sum of low rank symmetric positive semi-definite and non-negative diagonal matrix. Let me ...